Add two numbers in LL

Intuition

Imagine you have two numbers written on paper, with the digits arranged backward:

Number 1: 3 -> 2 -> 1 (Represents 123)
Number 2: 4 -> 5 -> 6 (Represents 654)

To add them, you'd start from the rightmost digits (ones place), add them up (1 + 4 = 5), then move left to the next pair (tens place: 2 + 5 = 7), and so on. If the sum of two digits is greater than or equal to 10, you'd carry over the '1' to the next digit position.

In this problem, the numbers are stored in linked lists, which are essentially chains of nodes, each holding a single digit. The linked lists are in reverse order, just like our example.

Approach

Simultaneous Traversal: Traverse both linked lists at the same time, node by node.

Digit-wise Addition: At each step, add the values stored in the current nodes from both lists. Also, add any carry-over from the previous addition.

Create New Node: Calculate the result digit by taking the modulo 10 of the sum. Create a new node to store this digit.

Carry Over: If the sum is 10 or greater, carry over the '1' to the next addition.

Update Pointers: Move the pointers of both lists to their next nodes, and the pointer of the result list to the newly created node.

Continue: Repeat steps 2-5 until you reach the end of both input lists. If there's a carry-over at the end, create one more node for it.

Note that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head's value.

Dry Run

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int data1) {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1) {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    //Function to add two numbers as linked list
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        /*Dummy node to act as the 
        starting point of the result list*/
        ListNode *dummy = new ListNode(); 
        /*Temp pointer to build 
        the result list*/
        ListNode *temp = dummy; 
        //Initialize carry
        int carry = 0;                    

        /*Iterate while there are nodes in l1 or l2, 
        or there's a carry to process*/
        while ((l1 != NULL || l2 != NULL) || carry) {
            int sum = 0;

            /*Add the value from l1 
            if available*/
            if (l1 != NULL) {
                sum += l1->val;
                l1 = l1->next;
            }

            /*Add the value from l2 
            if available*/
            if (l2 != NULL) {
                sum += l2->val;
                l2 = l2->next;
            }

            //Add the carry
            sum += carry;
            //Update the carry
            carry = sum / 10;             

            /* Create a new node with the digit value 
            and attach it to the result list*/
            ListNode *node = new ListNode(sum % 10);
            temp->next = node;
            /*Move to the 
            next position in the result list*/
            temp = temp->next;             
        }
        /*Return the result list
        skipping the dummy node*/
        return dummy->next;                
    }
};

// Function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    //Manual creation of linked list
    ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
    ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

    //Instance of solution class
    Solution solution;
    ListNode* result = solution.addTwoNumbers(l1, l2);

    // Print the result
    printList(result);

    return 0;
}
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int data1) {
        val = data1;
        next = null;
    }
    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to add two numbers as linked list
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        /* Dummy node to act as the
        starting point of the result list */
        ListNode dummy = new ListNode(0);
        /* Temp pointer to build
        the result list */
        ListNode temp = dummy;
        // Initialize carry
        int carry = 0;

        /* Iterate while there are nodes in l1 or l2,
        or there's a carry to process */
        while (l1 != null || l2 != null || carry != 0) {
            int sum = 0;

            /* Add the value from l1
            if available */
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            /* Add the value from l2
            if available */
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            // Add the carry
            sum += carry;
            // Update the carry
            carry = sum / 10;

            /* Create a new node with the digit value
            and attach it to the result list */
            ListNode node = new ListNode(sum % 10);
            temp.next = node;
            /* Move to the
            next position in the result list */
            temp = temp.next;
        }
        /* Return the result list
        skipping the dummy node */
        return dummy.next;
    }
}

// Function to print the linked list
public static void printList(ListNode head) {
    while (head != null) {
        System.out.print(head.val + " ");
        head = head.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    // Manual creation of linked list
    ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
    ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

    // Instance of solution class
    Solution solution = new Solution();
    ListNode result = solution.addTwoNumbers(l1, l2);

    // Print the result
    printList(result);
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to add two numbers as linked list
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # Dummy node to act as the starting point of the result list
        dummy = ListNode(0)
        # Temp pointer to build the result list
        temp = dummy
        # Initialize carry
        carry = 0

        # Iterate while there are nodes in l1 or l2, or there's a carry to process
        while l1 or l2 or carry:
            sum = 0

            # Add the value from l1 if available
            if l1:
                sum += l1.val
                l1 = l1.next

            # Add the value from l2 if available
            if l2:
                sum += l2.val
                l2 = l2.next

            # Add the carry
            sum += carry
            # Update the carry
            carry = sum // 10

            # Create a new node with the digit value and attach it to the result list
            node = ListNode(sum % 10)
            temp.next = node
            # Move to the next position in the result list
            temp = temp.next

        # Return the result list skipping the dummy node
        return dummy.next

# Function to print the linked list
def printList(head: ListNode):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    # Manual creation of linked list
    l1 = ListNode(2, ListNode(4, ListNode(3)))
    l2 = ListNode(5, ListNode(6, ListNode(4)))

    # Instance of solution class
    solution = Solution()
    result = solution.addTwoNumbers(l1, l2)

    # Print the result
    printList(result)
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to add two numbers as linked list
    addTwoNumbers(l1, l2) {
        /* Dummy node to act as the 
        starting point of the result list */
        let dummy = new ListNode(0);
        /* Temp pointer to build 
        the result list */
        let temp = dummy;
        // Initialize carry
        let carry = 0;

        /* Iterate while there are nodes in l1 or l2, 
        or there's a carry to process */
        while (l1 !== null || l2 !== null || carry !== 0) {
            let sum = 0;

            /* Add the value from l1 
            if available */
            if (l1 !== null) {
                sum += l1.val;
                l1 = l1.next;
            }

            /* Add the value from l2 
            if available */
            if (l2 !== null) {
                sum += l2.val;
                l2 = l2.next;
            }

            // Add the carry
            sum += carry;
            // Update the carry
            carry = Math.floor(sum / 10);

            /* Create a new node with the digit value 
            and attach it to the result list */
            let node = new ListNode(sum % 10);
            temp.next = node;
            /* Move to the 
            next position in the result list */
            temp = temp.next;
        }
        /* Return the result list
        skipping the dummy node */
        return dummy.next;
    }
}

// Function to print the linked list
function printList(head) {
    let current = head;
    while (current !== null) {
        process.stdout.write(current.val + " ");
        current = current.next;
    }
    console.log();
}

const l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
const l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

const solution = new Solution();
const result = solution.addTwoNumbers(l1, l2);

printList(result);

Complexity Analysis

Time Complexity: O(max(M, N)) Here, M and N represent the sizes of the linked lists l1 and l2, respectively. The algorithm traverses both lists at most once, hence the time complexity depends on the length of the longer list.

Space Complexity: O(max(M,N)) The length of the new list is at most max(M, N)+1.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts