Add Two Numbers Represented Using Linked Lists - Java Solution

1. Introduction

In this blog post, we explore the "Add Two Numbers" problem, a common algorithmic programming challenge involving adding two numbers represented as linked lists. We will solve this problem using Java, offering a deep dive into handling data structures like singly-linked lists.

Problem

Given two non-empty linked lists representing two non-negative integers, where the digits are stored in reverse order and each node contains a single digit, your task is to add these numbers and return the sum as a linked list. Assume there are no leading zeros, except for the number 0 itself.

2. Solution Steps

1. Create a dummy head node to simplify list manipulation.

2. Iterate through both lists, adding corresponding digits and any carry from the previous sum.

3. For each sum, create new nodes, handling carry-over for sums above 9.

4. Continue this process until both lists are fully traversed.

5. If there's a remaining carry, create an additional node for it.

3. Code Program

// Node structure for linked list
public class ListNode {
    int val; // Value of the node
    ListNode next; // Reference to the next node

    // Constructor to initialize the node with a value
    ListNode(int x) { val = x; }

    // Method to print the linked list starting from this node
    void printList() {
        ListNode temp = this;
        while(temp != null) {
            System.out.print(temp.val + " "); // Print the value of the current node
            temp = temp.next; // Move to the next node
        }
        System.out.println();
    }
}

// Solution class to add two numbers
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // Dummy head to simplify list manipulation
        ListNode p = l1, q = l2, curr = dummyHead; // Pointers for iterating over lists
        int carry = 0; // Variable to store carry

        // Iterate until both lists are fully traversed
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0; // Value from list l1 or 0 if null
            int y = (q != null) ? q.val : 0; // Value from list l2 or 0 if null
            int sum = carry + x + y; // Sum of current digits and carry
            carry = sum / 10; // Update carry for the next iteration
            curr.next = new ListNode(sum % 10); // Create new node with the single digit
            curr = curr.next; // Move to the next node in the result list

            if (p != null) p = p.next; // Move to the next node in l1
            if (q != null) q = q.next; // Move to the next node in l2
        }

        // Handle remaining carry
        if (carry > 0) {
            curr.next = new ListNode(carry); // Create a node with the remaining carry
        }
        return dummyHead.next; // Return the sum list, excluding the dummy head
    }
}

// Example usage and testing
public class Main {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2); // First node of first list
        l1.next = new ListNode(4); // Second node of first list
        l1.next.next = new ListNode(3); // Third node of first list

        ListNode l2 = new ListNode(5); // First node of second list
        l2.next = new ListNode(6); // Second node of second list
        l2.next.next = new ListNode(4); // Third node of second list

        Solution solution = new Solution();
        ListNode result = solution.addTwoNumbers(l1, l2);
        result.printList(); // Print the result list
    }
}

Output:

7 0 8

Explanation:

The input lists (2 -> 4 -> 3) and (5 -> 6 -> 4) represent the numbers 342 and 465, respectively. When added, they equal 807. Since the lists store numbers in reverse, the output list is (7 -> 0 -> 8), representing the sum of 807.