Add two numbers represented by linked lists

Given two numbers represented by two linked lists of size N and M. The task is to return a sum list. The sum list is a linked list representation of the addition of two input numbers from the last.

Example 1:

Input:
N = 2
valueN[] = {4,5}
M = 3
valueM[] = {3,4,5}
Output: 3 9 0
Explanation:
For the given two linked
list (4 5) and (3 4 5), after adding
the two linked list resultant linked
list will be (3 9 0).

Example 2:

Input:
N = 2
valueN[] = {6,3}
M = 1
valueM[] = {7}
Output: 7 0
Explanation:
For the given two linked
list (6 3) and (7), after adding the
two linked list resultant linked list
will be (7 0).

Your Task:
The task is to complete the function addTwoLists() which has node reference of both the linked lists and returns the head of the new list.

Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(Max(N,M))

Constraints:
1 <= N, M <= 5000

code:

class Node:
def __init__(self, val):
self.data = val
self.next = None
class LinkedList():
def __init__(self):
self.head = None
def insert(self,data):
if self.head is None:
self.head = Node(data)
return
temp = self.head
while temp:
if temp.next == None:
temp.next = Node(data)
return
else:
temp = temp.next
def print_list(self):
temp = self.head
while temp:
print(temp.data)
temp = temp.next


root1 = LinkedList()
root2 = LinkedList()

for i in '77032':
root1.insert(int(i))
for j in '29660':
root2.insert(int(j))




'''
root1.insert(4)
root1.insert(5)
root2.insert(3)
root2.insert(4)
root2.insert(5)'''
def push(root, data):
new_node = Node(data)
if root.head == None:
root.insert(data)
return
new_node.next = root.head
root.head = new_node
return
def print_list(head):
while head:
print(head.data)
head = head.next
return

'''test_root = LinkedList()
test_root.insert(3)
delete_last(test_root.head)
print_list(test_root.head)'''

'''
0. define a zero node, a new_linked_list and carry = 0
1. go to the last digit in lists
2. add these two digits along wth carry. If any one digit is None, use zero node
3. change the carry value
4. push the sum to the new_linked_list
5. delete these two digits
6. go to step 1
'''
def list_adder(head1,head2):
def push(root, data):
new_node = Node(data)
if root.head == None:
root.insert(data)
return
new_node.next = root.head
root.head = new_node
return
def delete_last(head):

if head.next is None:
head.data = None
return head
while head.next.next:
head = head.next
head.next = head.next.next
return
zero_node = LinkedList()
zero_node.insert(0)
new_linked_list = LinkedList()
temp1 = head1
temp2 = head2
i=0
t1_changed = False
t2_changed = False
carry = 0
while temp1 or temp2:
while temp1.next:
temp1 = temp1.next
while temp2.next:
temp2 = temp2.next
t1 = temp1
t2 = temp2
if t1.data == None:
t1_changed = True
t1 = zero_node.head
if t2.data == None:
t2_changed = True
t2 = zero_node.head
if t1_changed and t2_changed:
if carry>0:
push(new_linked_list, carry)
break
#print('working with last digits', t1.data, t2.data)
Sum = t1.data+t2.data+carry
if Sum>9:
Sum = str(Sum)
Sum,carry = int(Sum[-1]),int(Sum[:-1])
else:
carry = 0
#new_linked_list.insert(Sum)
push(new_linked_list, Sum)
delete_last(head1)
delete_last(head2)
temp1 = head1
temp2 = head2
return new_linked_list.head
print_list(list_adder(root1.head,root2.head))
#print_list(root1.head)

--

--

--

Looking for my next opportunity to make change in a BIG way

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Docker: Intro

10 Ways to Make Unsuccessful Tech Project

Creating A Landscape Oriented Android Application

The Beauty of Pattern Matching in Elixir

Laravel 8.0 Form Validation Example

Test Automation: A Step-by-Step Guide for Building an Automated UI Testing Framework

Forward Kinematics using Orocos KDL

Making Complex Conditional Formatting EASY!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sairam Penjarla

Sairam Penjarla

Looking for my next opportunity to make change in a BIG way

More from Medium

Arithmetic Operators On Python

Checking file permissions in Python

Google COLAB local runtime ASAP

Learning Python - Modules and Packages