Solution to LeetCode 2 Add two numbers & 61 Rotate list, and a template for creating a Linked List
LeetCode 2
Add two numbers (Medium). [link]
Usually we use “dummy head” to track head when creating a new linked list. When doing addition, we need to assume big integer addition and high-precision math operation, so 32-bit or 64-bit are not satisfying, we usually resort to linked list, array, or string. Special scenarios: 1) adding 2 numbers with different lengths (123 + 4567), 2) the result has more digits (99 + 99 = 198).
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy = tail = ListNode(0)
SUM = 0
carry = 0
while l1 or l2:
SUM = (l1.val if l1 else 0) + (l2.val if l2 else 0)
SUM += carry
carry = (SUM >= 10)
tail.next = ListNode(SUM % 10)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
if carry: # Don't forget additional 1 added at the end when carry == 1.
tail.next = ListNode(1)
return dummy.next
Another solution without carry.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy = tail = ListNode(0)
SUM = 0
while l1 or l2:
SUM += (l1.val if l1 else 0) + (l2.val if l2 else 0)
tail.next = ListNode(SUM % 10)
tail = tail.next
SUM //= 10 # carry to the next digit
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
if SUM == 1: # Don't forget additional 1 added at the end when carry == 1.
tail.next = ListNode(1)
return dummy.next
Another solution without consider additional carry-over. If l1 and l2 are both None while SUM = 1, there is still a while loop to add 1 to the end.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy = tail = ListNode(0)
SUM = 0
while l1 or l2 or SUM:
SUM += (l1.val if l1 else 0) + (l2.val if l2 else 0)
tail.next = ListNode(SUM % 10)
tail = tail.next
SUM //= 10 # carry to the next digit
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
LeetCode 61
Rotate list (Medium). [link]
It is possible k > len(list), rotating k times is the same as rotating k % len(list) times. The Linked list is singly directed, so we need to store the previous node of the current node. The previous node of new head is the (len(list)-k)th node of the original linked list.
The time complexity is O(n), the space complexity is O(1).
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head:
return head
tail = head
l = 1
while tail.next: # calculate length
tail = tail.next
l += 1
k = k % l # modulo operation
if k == 0:
return head
prev = head
for _ in range(l - k - 1): # find the (l-k)th node
prev = prev.next
newHead = prev.next # find the new head
tail.next = head # link tail to head
prev.next = None # link prev node to None
return newHead
Template for Addition of Linked Lists
dummy = tail = ListNode(0)
carry = 0
while l1 or l2 or carry: # carry: 0 or 1
sum = l1.val + l2.val + carry # need to add 0 if lengths differ
tail.next = ListNode(sum % 10)
tail = tail.next
carry = sum // 10
l1, l2 = l1.next, l2.next
return dummy.next
Time complexity O(max(n,m)), space complexity O(max(n,m)).
