Python Challenges: Add Two Numbers

Last update on December 21 2024 07:49:53 (UTC/GMT +8 hours)

There are two non-empty linked lists where every node contains non-negative single digit.
Write a Python program to reverse and add the numbers of the two linked lists.

Difficulty: Medium.
Company: Amazon, Google, Bloomberg, Microsoft, Adobe, Apple, Oracle and More

Input:
First linked list: 4->3->2 // represents number 234
Second linked list: 7>2->5 // represents number 527
Output: 167
[ 234 + 527 = 761]
Explanation: 234 + 527 = 761

Input:
First linked list: 2->4->3 // represents number 342
Second linked list: 5>6->4 // represents number 465
Output: [7,0,8]
[342 + 465 = 807]
Explanation: 342 + 465 = 807.

Input:
List1: 5>4->3->1->2 // represents number 21345
List2: 4->2->1 // represents number 124
Output: 96412
[ 21345 + 124 = 21469]
Explanation: 21345 + 124 = 21469.

Input:
List1: 7->0->1 // represents number 107
List2: 4->2->0 // represents number 24
Output: 131
[107 + 24 = 131]
Explanation: 107 + 24 = 131.

Sample Solution:

Python Code:

class Node:
    # Singly linked node
    def __init__(self, data=None):
        self.data = data
        self.next = None
class singly_linked_list:
    def __init__(self):
        # Createe an empty list
        self.head = None
        self.tail = None
        self.count = 0
    def iterate_item(self):
        # Iterate the list.
        current_item = self.head
        while current_item:
            val = current_item.data
            current_item = current_item.next
            yield val
    def append_item(self, data):
        #Append items on the list
        node = Node(data)
        if self.tail:
            self.tail.next = node
            self.tail = node
        else:
            self.head = node
            self.tail = node
        self.count += 1
        
    def addTwoLists(self, list1, list2):
        str_l1, str_l2 = '', ''
        while list1:
            str_l1 += str(list1.data)
            list1 = list1.next
        while list2:            
            str_l2 += str(list2.data)
            list2 = list2.next
        int_l1 = int(str_l1[::-1])
        int_l2 = int(str_l2[::-1])       
        return list(map(int, str(int_l1 + int_l2)[::-1])) 
    
list1 = singly_linked_list()
list1.append_item(5)
list1.append_item(4)
list1.append_item(3)
list1.append_item(1)
list1.append_item(2)
#--------------------------
list2 = singly_linked_list()
list2.append_item(4)
list2.append_item(2)
list2.append_item(1)
print("Linked list1:")
for val in list1.iterate_item():
    print(val, end = " ")
print("\nLinked list2:")
for val in list2.iterate_item():
    print(val, end = " ")

res = singly_linked_list()
print("\n\nResult: ",res.addTwoLists(list1.head, list2.head))

Sample Output:

Linked list1:
5 4 3 1 2 
Linked list2:
4 2 1 

Result:  [9, 6, 4, 1, 2]

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to find different ways where £2 be made using any number of coins.
Next: Write a Python program to calculate sum of all positive, negative integers present in a given string.