Description
Given a non-negative integer represented as a linked list of digits, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list.
Example 1:
Input: head = [1,2,3]
Output: [1,2,4]
Example 2:
Input: head = [0]
Output: [1]
Constraints:
- The number of nodes in the linked list is in the range
[1, 100].
0 <= Node.val <= 9- The number represented by the linked list does not contain leading zeros except for the zero itself.
Solutions
Solution 1: Linked List Traversal
We first set a dummy head node dummy, initially with a value of 0, and the successor node of dummy is the linked list head.
Next, we traverse the linked list starting from the dummy head node, find the last node that is not 9, increment its value by 1, and set the values of all nodes after this node to 0.
Finally, we check if the value of the dummy head node is 1. If it is 1, we return dummy; otherwise, we return the successor node of dummy.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
PythonJavaC++GoTypeScript
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def plusOne(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
target = dummy
while head:
if head.val != 9:
target = head
head = head.next
target.val += 1
target = target.next
while target:
target.val = 0
target = target.next
return dummy if dummy.val else dummy.next(code-box)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode plusOne(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode target = dummy;
while (head != null) {
if (head.val != 9) {
target = head;
}
head = head.next;
}
++target.val;
target = target.next;
while (target != null) {
target.val = 0;
target = target.next;
}
return dummy.val == 1 ? dummy : dummy.next;
}
}(code-box)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* plusOne(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* target = dummy;
for (; head; head = head->next) {
if (head->val != 9) {
target = head;
}
}
target->val++;
for (target = target->next; target; target = target->next) {
target->val = 0;
}
return dummy->val ? dummy : dummy->next;
}
};(code-box)
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func plusOne(head *ListNode) *ListNode {
dummy := &ListNode{0, head}
target := dummy
for head != nil {
if head.Val != 9 {
target = head
}
head = head.Next
}
target.Val++
for target = target.Next; target != nil; target = target.Next {
target.Val = 0
}
if dummy.Val == 1 {
return dummy
}
return dummy.Next
}(code-box)
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function plusOne(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let target = dummy;
while (head) {
if (head.val !== 9) {
target = head;
}
head = head.next;
}
target.val++;
for (target = target.next; target; target = target.next) {
target.val = 0;
}
return dummy.val ? dummy : dummy.next;
}(code-box)
