Add two numbers as LinkedList

Problem Overview

The "Add Two Numbers" problem on LeetCode is a classic question that helps in understanding the manipulation of linked lists. The problem requires you to add two numbers represented by two non-empty linked lists. In these linked lists, each node contains a single-digit integer and the digits are stored in reverse order. Your task is to return the sum as a linked list in the same reversed order.

Understanding the Problem

• You are given two linked lists where each list represents a non-negative integer in reverse order.
• Each node holds one digit and the more significant digit comes after less significant ones (the head represents the least significant digit).
• You need to compute the sum of these two numbers and return the result as a new linked list, also in reverse order.

The essential thing to note is that since the numbers might have differing lengths, you should consider a carry that occurs when the sum of digits exceeds 9.

Key DSA Concepts and Theory

Linked Lists

A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a reference (or a pointer) to the next node in the sequence. Unlike arrays, linked lists allow for efficient insertion and removal of elements as they don’t require shifting elements.

Types of Linked Lists

• Singly Linked List: Each node contains data and a pointer to the next node.
• Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node.
• Circular Linked List: The last node points back to the first node, creating a circle-like structure.

Addition with Carry

When adding two numbers, if the sum of two single digits exceeds 9, a carry is generated which must be added to the sum of the next pair of digits.

Solution Approach

To solve this problem, we need to iterate through both linked lists simultaneously, digit by digit, and maintain a carry that results from the summation of digits and carry from the previous step. Here’s a step-by-step approach:

1. Initialize a dummy node to help simplify the edge cases.
2. Iterate through both linked lists:
   • Extract values from each node, defaulting to 0 if the node is null.
   • Sum the two values with any carry from the previous iteration.
   • Create a new node for the current digit (use modulo operation).
   • Update the carry for the next iteration (use integer division).
3. After the loop, if there is still a carry, append a new node with the carry value.
4. Return the next node of the dummy node, as it serves as the head of the linked list representing the sum.

C++ Solution

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode *current = &dummy;
    int carry = 0;
    
    while (l1 != nullptr || l2 != nullptr || carry) {
        int sum = carry;
        
        if (l1 != nullptr) {
            sum += l1->val;
            l1 = l1->next;
        }
        
        if (l2 != nullptr) {
            sum += l2->val;
            l2 = l2->next;
        }
        
        carry = sum / 10;
        current->next = new ListNode(sum % 10);
        current = current->next;
    }
    
    return dummy.next;
}

Java Solution

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }
        
        return dummy.next;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(max(N, M)), where N and M are the lengths of l1 and l2. We iterate over both lists once.
• Space Complexity: O(max(N, M)), as we are creating a new linked list to store the result.

Common Mistakes to Avoid

• Not accounting for when the final carry is greater than zero; this requires adding an additional node.
• Forgetting to check if one of the linked lists is shorter than the other and handling it appropriately.

Similar Problems on LeetCode

1. Add Two Numbers II - LeetCode 445
2. Multiply Strings - LeetCode 43
3. Reverse Linked List - LeetCode 206

Additional Resources and References

• MIT OpenCourseWare on Linked Lists
• GeeksforGeeks - Linked List Basics
• YouTube - How to solve add two numbers using linked lists

This article gives you a comprehensive guide to solving the "Add Two Numbers" problem, explaining the theory behind linked lists, implementation details, and potential pitfalls to avoid, as well as providing additional practice problems and resources for further study.