Add Two Numbers - Java Solution

1. Introduction

This blog post delves into the "Add Two Numbers" problem, a fundamental question in linked list manipulation. The challenge involves adding two non-negative integers represented by two linked lists, where each node contains a single digit, and the digits are stored in reverse order. This problem is a classic exercise for understanding linked list operations and number manipulation.

Problem

Given two non-empty linked lists representing two non-negative integers, with digits stored in reverse order and each node containing a single digit, the task is to add the two numbers and return the sum as a linked list. Leading zeros are not present except in the number 0 itself.

2. Solution Steps

1. Initialize a dummy head node to simplify edge case handling.

2. Create a pointer current for the resulting list and variables for carrying over (carry) and sum.

3. Iterate through both lists simultaneously, adding corresponding digits along with the carry.

4. If one list is longer, continue the iteration for the remaining nodes.

5. After processing both lists, if there's a remaining carry, create a new node for it.

6. Return the linked list starting after the dummy head.

3. Code Program

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

public class AddTwoNumbers {
    public static void main(String[] args) {
        // Example use case
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode result = addTwoNumbers(l1, l2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    // Function to add two numbers represented by linked lists
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummyHead.next;
    }
}

Output:

7 0 8

Explanation:

1. addTwoNumbers: This function performs the addition of two numbers represented by linked lists l1 and l2.

2. A dummy head node is used to handle edge cases gracefully and simplify the code.

3. The function iterates through both lists, adding the corresponding digits and handling the carry from the previous addition.

4. If one list is longer than the other, it continues to process the remaining digits.

5. After iterating through both lists, if there's any remaining carry, it creates a new node for this carry.

6. The result is a new linked list representing the sum of the two numbers, which is returned starting from the node after the dummy head.

7. This approach efficiently manages digit-by-digit addition while taking care of carries and varying lengths of input lists.