Add two numbers represented by linked lists | Forward Method

As we've discussed in the previous post, this problem is almost the same as the previous but digits are stored in a forward manner.

Problem: We have two numbers represented by linked lists, where each node contains a single digit. The digits are stored in forward 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: 1 -> 0 -> 5 -> 5 -> 4 (That is (9876 + 678) = 10554)

Important Note

One linked list may be shorter than the other same as the example given here. Here two lists are (9 -> 8 -> 7 -> 6) and (6 -> 7 -> 8). Remember the 6 should be matched with the 8, the 7 should be matched with the 7, and the 8 to 6.

Let's see the picture given below to better understand.

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class linked_list:
    def __init__(self):
        self.head = None

    def addfinalList(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 addNode(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.addNode(sum)
           
            if flist is not None:
                flist = flist.next
            if slist is not None:
                slist = slist.next

        if carry > 0:
            self.addNode(carry)
    
if __name__ == "__main__":
    flist = linked_list()
    slist = linked_list()

    # Declaring a list to show the actual 
    # order of the data stored 
    # in the linked list
    view = []

    flist.addNode(9)
    flist.addNode(8)
    flist.addNode(7)
    flist.addNode(6)
    
    view = ['9', '8', '7', '6']

    print("~Forward Method~\n")

    print("Data from the first linked list:")
    print(view, end="\n")

    # Clear the list so that we can use it again
    # to reduce space complexity.
    view.clear()

    slist.addNode(6)
    slist.addNode(7)
    slist.addNode(8)

    view = ['6', '7', '8']

    print("Data from the second linked list:")
    print(view, end="\n")

    result = linked_list()
    result.addTwoLists(flist.head,slist.head)

    print("The Final Linked List is:")
    result.printNode()

Output

~Forward Method~

Data from the first linked list:
['9', '8', '7', '6']
Data from the second linked list:
['6', '7', '8']
The Final Linked List is:
1->0->5->5->4->

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 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.