Teaching Kids Programming – Adding Two Linked List


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a singly linked list l0 and another linked list l1, each representing a number with least significant digits first, return the summed linked list. Note: Each value in the linked list is guaranteed to be between 0 and 9.

Constraints
n ≤ 100,000 where n is the number of nodes in l0
m ≤ 100,000 where m is the number of nodes in l1
Example 1
Input
Visualize
l0 = [6, 4]
l1 = [4, 7]
Output
Visualize
[0, 2, 1]
Explanation
This is 46 + 74 = 120

One solution (adding two linked list) would be first to convert linked list to numbers, and then add them, and convert the numbers (result) to linked list. This introduces overheads in conversion not to mention that in most programming languages, the numbers are size-limited either 34 bit or 64 bit. In Python, luckily this would work as numbers are not limited by sizes.

Algorithm to Add Two Linked Lists

We need to record the carry-over, and add the digits by digits (from the least significant digit). This process iterates until both linked lists are exhausted and carry-over is zero.

Luckily, the link lists are represented in reverse order where the least signifiant digits come first, so we can just start from the head of both linked lists and add them along the way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoLinkedLists(self, l0, l1):
        dummy = LLNode(-1)
        p = dummy
        c = 0
        while l0 or l1 or c:
            v = c
            if l0:
                v += l0.val
                l0 = l0.next
            if l1:
                v += l1.val
                l1 = l1.next
            p.next = LLNode(v % 10)
            c = v // 10
            p = p.next
        return dummy.next
# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoLinkedLists(self, l0, l1):
        dummy = LLNode(-1)
        p = dummy
        c = 0
        while l0 or l1 or c:
            v = c
            if l0:
                v += l0.val
                l0 = l0.next
            if l1:
                v += l1.val
                l1 = l1.next
            p.next = LLNode(v % 10)
            c = v // 10
            p = p.next
        return dummy.next

The time complexity is O(M+N) where M and N is the number of the nodes in each linked list respectively. The space complexity is O(Max(M, N)).

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
449 words
Last Post: Hash Algorithm to Check A List Containing Almost Same Strings (Differ By One Character)
Next Post: Breadth First Search Algorithm to Compute the Leftmost Deepest Tree Node in a Binary Tree

The Permanent URL is: Teaching Kids Programming – Adding Two Linked List

One Response

  1. Shamalama

Leave a Reply