Question:

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 it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

Answer:

To solve this problem, we can traverse the two linked lists simultaneously and add the digits at each position, considering their carry overs.

Here are the step-by-step instructions to solve this problem:

1. Create a dummy node to store the head of the result linked list. Also, create a current node initialized with the dummy node.
2. Initialize two pointers, p and q, to the heads of the input linked lists representing the two numbers to be added.
3. Initialize two variables, carry and sum, to store the carry over and sum at each position.
4. Traverse the linked lists until both p and q become null. For each node:
   • Set the value of num1 to the value of node p if it exists, otherwise set it to 0.
   • Set the value of num2 to the value of node q if it exists, otherwise set it to 0.
   • Calculate the sum of num1, num2, and the carry.
   • Update the carry by dividing the sum by 10.
   • Create a new node with the value of the sum modulo 10 and set it as the next node of the current node.
   • Move the current node pointer to the next node.
   • Move both p and q pointers to their next nodes if they exist.
5. After the loop ends, check if there is any remaining carry. If there is, create a new node with the value of the carry and set it as the next node of the current node.
6. Return the next node of the dummy node, which is the head of the result linked list.

Here is the implementation of the above algorithm in Python:

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

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    carry = 0
    
    p = l1
    q = l2

    while p or q:
        num1 = p.val if p else 0
        num2 = q.val if q else 0
        summ = num1 + num2 + carry
        carry = summ // 10
        curr.next = ListNode(summ % 10)
        curr = curr.next
        if p:
            p = p.next
        if q:
            q = q.next

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

    return dummy.next

The time complexity of this algorithm is O(max(m, n)), where m and n are the lengths of the two input linked lists.