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.

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.