Problem: We have two numbers represented by linked lists, where each node contains a single digit. The digits are stored in reverse order. Write a function to add two numbers represented by linked lists and returns the sum as a linked list.
Example
9 -> 8 -> 7 -> 6
+
6 -> 7 -> 8
Result is: 5 -> 6 -> 6 -> 7 (That is (6789 + 876) = 7665)
Solution
Step 1: Traverse both lists from start to end until both linked lists reached the end.
Step 2: Add each node value from the respective list.
Step 3: If (Sum < 10), store it into a different linked list. If (Sum > 9), then store (Sum%10) instead of Sum and add 1 as carry to the next node while adding their values.
Step 4: If one list reached the end and another is not, then take 0 as the node value of that list.
Code
class Node:
def __init__(self,data):
self.data = data
self.next = None
class linked_list:
def __init__(self):
self.head = None
def addNode(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
temp = self.head
while(temp.next):
temp = temp.next
temp.next = new_node
def addToFinalList(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def printNode(self):
temp = self.head
while(temp):
print(temp.data, end='->')
temp = temp.next
print("\n")
def addTwoLists(self, flist, slist):
carry = 0
while(flist is not None or slist is not None):
fdata = 0 if flist is None else flist.data
ldata = 0 if slist is None else slist.data
sum = (carry + fdata + ldata)
if sum < 10:
carry = 0
else:
carry = 1
sum = sum % 10
if self.head is None:
self.head = Node(sum)
else:
self.addToFinalList(sum)
if flist is not None:
flist = flist.next
if slist is not None:
slist = slist.next
if carry > 0:
self.addToFinalList(carry)
if __name__ == "__main__":
flist = linked_list()
slist = linked_list()
flist.addNode(9)
flist.addNode(8)
flist.addNode(7)
flist.addNode(6)
print("~Reverse Method~\n")
print("First Linked List is:")
flist.printNode()
slist.addNode(6)
slist.addNode(7)
slist.addNode(8)
print("Second Linked List is: ")
slist.printNode()
result = linked_list()
result.addTwoLists(flist.head,slist.head)
print("Final Linked List is: ")
result.printNode()
Output
~Reverse Method~
First Linked List is:
9->8->7->6->
Second Linked List is:
6->7->8->
Final Linked List is:
7->6->6->5->
Complexity Analysis
Time Complexity: O(n), where n is the total number of nodes or length of the largest linked list.
Space Complexity: O(n) or O(n + 1), where n is the length of the temporary linked list used to store the Sum values and it depends on the number of the node of the largest linked list. Situation (n + 1) can arise when an extra node needs to be generated when carry arises at the last node.
Note: This problem is taken from "cracking the coding interview" by Gayle Laakmann Mcdowell, Interview Questions, chapter 2, problem #2.5.