Linked List
Math
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
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 # 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 : ListNode ) -> 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 /**
* 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 ;
while ( head ) {
if ( head -> val != 9 ) target = head ;
head = head -> next ;
}
++ target -> val ;
target = target -> next ;
while ( target ) {
target -> val = 0 ;
target = target -> next ;
}
return dummy -> val == 1 ? dummy : dummy -> next ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 /**
* 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 ++
target = target . Next
for target != nil {
target . Val = 0
target = target . Next
}
if dummy . Val == 1 {
return dummy
}
return dummy . Next
}
GitHub