Add two numbers represented by linked lists | Reverse Method

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.

Add two numbers represented by linked lists and the digits are stored in reverse order. The problem has been solved here using python.

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.

Subhankar Rakshit

Meet Subhankar Rakshit, a Computer Science postgraduate (M.Sc.) and the creator of PySeek. Subhankar is a programmer, specializes in Python language. With a several years of experience under his belt, he has developed a deep understanding of software development. He enjoys writing blogs on various topics related to Computer Science, Python Programming, and Software Development.

Post a Comment (0)
Previous Post Next Post