Add Two Numbers Represented as Linked List

In this article, we will solve the problem of adding two numbers represented as linked lists.

So we are given the heads of two singly linked lists that represent two integers. The digits are stored in reverse order and every node will contain a single digit. Our task is to add the two numbers and return the sum as a linked list.

Example:

Input: 

l1 = [1 -> 0 -> 3]  l2 = [5 -> 6 -> 4]

Output: 6 -> 6 -> 7

Explanation: 301 + 465 = 766 (digits are in reverse order).

Solution:

To solve this problem, we will follow these steps:

1.    Initialize a Dummy Node:

o   Create a dummy node that will act as the starting point of the result linked list.

o   Initialize a pointer current to this dummy node.

o   Initialize a variable carry to 0 to handle any carry-over during addition.

2.    Traverse Both Linked Lists:

o   Loop through both linked lists until both are null.

o   For each node, sum the values of the corresponding nodes from both linked lists and the carry.

o   Calculate the new digit and the new carry.

o   Create a new node with the computed new digit and append it to the result linked list.

3.    Handle Remaining Carry:

o   If there is any remaining carry after the loop, create a new node with the carry value and append it to the result linked list.

4.    Return Result:

o   Return the next node of the dummy node, which is the head of the resultant linked list.

Explanation:

1.    Initialize a Dummy Node:

o   A dummy node is used to simplify edge cases and makes it easier to return the head of the resulting list.

o   current pointer is used to build the resulting list.

o   carry is initialized to 0.

2.    Traverse Both Linked Lists:

o   Loop through both linked lists until both are exhausted.

o   For each node in the lists, retrieve the values (if a list is exhausted, use 0).

o   Calculate the sum of the values and the carry.

o   Compute the new digit and the carry-over.

3.    Handle Remaining Carry:

o   If there is a carry left after the loop, create a new node with the carry value and append it to the result list.

Time Complexity: O(max(m,n))

Space Complexity: O(max(m,n))