forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 65
/
plus-one-linked-list.py
66 lines (56 loc) · 1.53 KB
/
plus-one-linked-list.py
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Time: O(n)
# Space: O(1)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# Two pointers solution.
class Solution(object):
def plusOne(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
dummy = ListNode(0)
dummy.next = head
left, right = dummy, head
while right.next:
if right.val != 9:
left = right
right = right.next
if right.val != 9:
right.val += 1
else:
left.val += 1
right = left.next
while right:
right.val = 0
right = right.next
return dummy if dummy.val else dummy.next
# Time: O(n)
# Space: O(1)
class Solution2(object):
def plusOne(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def reverseList(head):
dummy = ListNode(0)
curr = head
while curr:
dummy.next, curr.next, curr = curr, dummy.next, curr.next
return dummy.next
rev_head = reverseList(head)
curr, carry = rev_head, 1
while curr and carry:
curr.val += carry
carry = curr.val / 10
curr.val %= 10
if carry and curr.next is None:
curr.next = ListNode(0)
curr = curr.next
return reverseList(rev_head)