Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a singly linked list l0 and another linked list l1, each representing a number with least significant digits first, return the summed linked list. Note: Each value in the linked list is guaranteed to be between 0 and 9.
Constraints
n ≤ 100,000 where n is the number of nodes in l0
m ≤ 100,000 where m is the number of nodes in l1
Example 1
Input
Visualize
l0 = [6, 4]
l1 = [4, 7]
Output
Visualize
[0, 2, 1]
Explanation
This is 46 + 74 = 120
One solution (adding two linked list) would be first to convert linked list to numbers, and then add them, and convert the numbers (result) to linked list. This introduces overheads in conversion not to mention that in most programming languages, the numbers are size-limited either 34 bit or 64 bit. In Python, luckily this would work as numbers are not limited by sizes.
Algorithm to Add Two Linked Lists
We need to record the carry-over, and add the digits by digits (from the least significant digit). This process iterates until both linked lists are exhausted and carry-over is zero.
Luckily, the link lists are represented in reverse order where the least signifiant digits come first, so we can just start from the head of both linked lists and add them along the way.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def addTwoLinkedLists(self, l0, l1): dummy = LLNode(-1) p = dummy c = 0 while l0 or l1 or c: v = c if l0: v += l0.val l0 = l0.next if l1: v += l1.val l1 = l1.next p.next = LLNode(v % 10) c = v // 10 p = p.next return dummy.next |
# class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def addTwoLinkedLists(self, l0, l1): dummy = LLNode(-1) p = dummy c = 0 while l0 or l1 or c: v = c if l0: v += l0.val l0 = l0.next if l1: v += l1.val l1 = l1.next p.next = LLNode(v % 10) c = v // 10 p = p.next return dummy.next
The time complexity is O(M+N) where M and N is the number of the nodes in each linked list respectively. The space complexity is O(Max(M, N)).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Hash Algorithm to Check A List Containing Almost Same Strings (Differ By One Character)
Next Post: Breadth First Search Algorithm to Compute the Leftmost Deepest Tree Node in a Binary Tree
Jon stole this code. Just wanted to let you know.