Add Two Numbers

Add Two Numbers

Given two non-empty linked lists representing two non-negative integers which store the digits in reverse order, add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

# input
[2,4,3]
[5,6,4]

#output
[7,0,8]

Review Questions:

1. How do you implement linked list?

2. What are some benefits and drawbacks of linked list compared to arrays?

3. Insertion and deletion of singly linked list?

Linked Lists

Linked list is a linear data structure that are linked using pointers. Linked lists have nodes that are connected to each other. Each node has data and the address of the next node.

Unlike array, the size of linked list is dynamic and insertion/deletion is easy by traversing through the head of the list. However, random access is impossible and there will be extra memory due to the pointer in the linked list.

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

Insertion Deletion

Approach 1:

Given that the numbers are in reversed order, the I think I would just have to:

1. Go through each nodes in the linked list
2. Sum up the values
3. Check if the sum is greater than 10
4. Account that carry-over to the next node

Implementation:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
        
class Solution:
    

    def addTwoNumbers(self,l1,l2):
        result = ListNode(0)
        temp = result
        carry = 0 # accounting for the carry-over
        
        while l1 or l2 or carry: # accounting for the fact where the last digit summation is greater than or equal to 10
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            carry, out = divmod(val1 + val2 + carry, 10)
            
            temp.next = ListNode(out)
            temp = temp.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
            
        return result.next

Complexity Analysis:

Time Complexity:O(max(m,n)) where m,n are length of l1, l2 respectively

Space Complexity: O(max(m,n))

Reflection

This was a great introductory question to linked list. Definitely a great review!