Sum of Linked Lists

Tags

Sum of Linked Lists

Category

Linked Lists

Difficulty

Medium

Problem Statement

Given two non-empty linked lists where each represents a non-negative integer with digits stored in reverse order (the head is the least significant digit), compute the sum of the two numbers and return the result as a new linked list, also in reverse order.

Intuition

Since the digits are stored in reverse order, the head of each list is the ones digit, the next node is the tens digit, and so on. This means we can add the numbers digit by digit from head to tail, exactly like manual addition from right to left. We track a carry value that propagates from one digit position to the next.

Approach

  1. Initialize a dummy head node for the result list and a pointer to track the current position.
  2. Initialize carry to 0.
  3. Traverse both lists simultaneously: a. Get the value from each list (0 if a list has been exhausted). b. Compute the sum = value1 + value2 + carry. c. The new digit is sum % 10; the new carry is sum / 10 (integer division). d. Create a new node with the digit and attach it to the result list. e. Advance pointers on both input lists (if not exhausted).
  4. After both lists are exhausted, if carry is still non-zero, add one more node.
  5. Return the node after the dummy head.

Pseudocode

function sumOfLinkedLists(list1, list2):
    dummyHead = new Node(0)
    current = dummyHead
    carry = 0
    p1 = list1
    p2 = list2

    while p1 is not null or p2 is not null or carry != 0:
        val1 = p1.value if p1 is not null else 0
        val2 = p2.value if p2 is not null else 0
        total = val1 + val2 + carry
        carry = total / 10
        digit = total % 10
        current.next = new Node(digit)
        current = current.next
        if p1 is not null: p1 = p1.next
        if p2 is not null: p2 = p2.next

    return dummyHead.next

Time & Space Complexity

  • Time: O(max(n, m)), where n and m are the lengths of the two linked lists. We traverse both lists fully once.
  • Space: O(max(n, m)) for the result linked list. The result has at most max(n, m) + 1 nodes (the extra node accounts for a final carry).

Key Insights

  • The reverse-order storage is what makes digit-by-digit addition natural; if the digits were in forward order, you would need to either reverse the lists first or use a stack.
  • The carry can only be 0 or 1 since the maximum sum of two digits plus a carry is 9 + 9 + 1 = 19.
  • Using a dummy head node simplifies the logic by avoiding special handling for the first node of the result list.

Edge Cases

  • Lists of different lengths (e.g., 3 digits + 5 digits): the shorter list is treated as having trailing zeros.
  • Sum produces a carry at the very end (e.g., 999 + 1 = 1000): an extra node is needed.
  • One or both lists represent the number 0 (a single node with value 0).
  • Both lists have a single node each.

Linked mentions