Problem: Add Two Numbers Represented by Linked Lists

Difficulty: Medium
Topics: Linked Lists, Mathematical Computation, Algorithm Design
Objective: Add two non-negative integers represented by linked lists and return the result as a linked list.

---

Problem Description

You are given two non-negative integers represented by two linked lists, where each node contains a single digit. 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 sum is returned as a linked list, where the digits are reversed.

---

Code Explanation

Step-by-Step Breakdown

The code defines a C++ class called Solution with a member function addTwoNumbers. The function adds two numbers represented by linked lists and returns the result as a new linked list.

1. Initialization:

• A dummy head node (dummyHead) is created to simplify list construction.
• A pointer (l3) is initialized to point to dummyHead.

2. Addition Loop:

• The loop continues as long as either of the linked lists has more digits or there's a carry left.
• For each iteration, the digits from l1 and l2 are extracted (or treated as 0 if the list is shorter).
• The sum is computed, and the carry is updated.

3. Creating the Result List:

• A new node with the current digit is created and appended to the result list.
• The pointer l3 is moved forward, and l1 and l2 are also advanced to the next nodes.

4. Final Result:

• The result starts from the node following the dummy head.
• The dummy head is deleted, and the final result is returned.

---

Test Cases

Test Case 1: Standard Addition

Input:
l1 = [2, 4, 3], l2 = [5, 6, 4]

Output:
[7, 0, 8]

Explanation:
342 + 465 = 807, which is returned as a linked list: [7, 0, 8].

---

Test Case 2: Addition with Carry Over

Input:
l1 = [9, 9, 9], l2 = [1, 1, 1]

Output:
[0, 1, 1, 1]

Explanation:
999 + 111 = 1110, which is returned as a linked list: [0, 1, 1, 1].

---

Test Case 3: Unequal Length Lists

Input:
l1 = [1, 2], l2 = [9, 9, 9]

Output:
[0, 2, 0, 1]

Explanation:
12 + 999 = 1011, which is returned as a linked list: [0, 2, 0, 1].

---

Test Case 4: One List is Empty

Input:
l1 = [], l2 = [5, 6, 4]

Output:
[5, 6, 4]

Explanation:
If one list is empty, the other list is returned as the result.

---

Test Case 5: Both Lists are Empty

Input:
l1 = [], l2 = []

Output:
[]

Explanation:
If both lists are empty, the result is an empty list.

---

— Written by Saurabh Patil • B.Tech CSE • Software Developer