LeetCode problem 2#: Add Two Numbers solution

LeetCode is a popular platform for practicing coding problems that cover a wide range of topics and difficulty levels. One common problem is “Add Two Numbers,” where you’re tasked with adding two numbers represented as linked lists. In this article, we’ll walk through the problem, discuss the algorithm, and provide solutions in both Java and Python.

Problem Description

The problem statement for “Add Two Numbers” on LeetCode is as follows:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

Example:

Input:

l1 = 2 -> 4 -> 3
l2 = 5 -> 6 -> 4

Output:

7 -> 0 -> 8

Explanation:

342 + 465 = 807

The Algorithm

The problem requires adding two numbers represented as linked lists. The digits are stored in reverse order, meaning that the 1’s digit is at the head of the list.

To solve this problem, we can use a simple iterative approach:

1. Initialize a dummy head node to 0 and set pointers p and q to the heads of l1 and l2 respectively.
2. Initialize a current pointer to the dummy head.
3. Initialize a carry variable to 0.
4. Traverse both linked lists simultaneously while p or q is not null.

• At each step, calculate the sum of the current digits along with the carry from the previous step.
• Update current with a new node containing the sum mod 10.
• Update carry with the integer division of the sum by 10.
• Move p and q to their respective next nodes.

1. If there is a carry remaining after processing all digits, add a new node with the carry value.
2. Return the next node of the dummy head, which will be the head of the resulting linked list.

Java Solution

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

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, current = dummyHead;
        int carry = 0;

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

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

        return dummyHead.next;
    }
}

Python Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_head = ListNode(0)
        p, q, current = l1, l2, dummy_head
        carry = 0

        while p is not None or q is not None:
            x = p.val if p is not None else 0
            y = q.val if q is not None else 0
            _sum = carry + x + y
            carry = _sum // 10
            current.next = ListNode(_sum % 10)
            current = current.next
            if p is not None: p = p.next
            if q is not None: q = q.next

        if carry > 0:
            current.next = ListNode(carry)

        return dummy_head.next

Conclusion

The “Add Two Numbers” problem on LeetCode is a great exercise in working with linked lists and basic arithmetic operations. The algorithm outlined above, along with the provided solutions in both Java and Python, should help you tackle this problem efficiently. Remember to understand the problem statement, design your algorithm, and test it with various inputs to ensure correctness. Happy coding!