Add two numbers represented by Linked Lists

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.

Input-Output Examples

Example 1:

  • Input:
    • List1: 2 -> 4 -> 3 -> NULL (represents 342)
    • List2: 5 -> 6 -> 4 -> NULL (represents 465)
  • Output: 7 -> 0 -> 8 -> NULL (represents 807)

Example 2:

  • Input:
    • List1: 0 -> NULL
    • List2: 0 -> NULL
  • Output: 0 -> NULL

Example 3:

  • Input:
    • List1: 9 -> 9 -> 9 -> NULL (represents 999)
    • List2: 1 -> NULL (represents 1)
  • Output: 0 -> 0 -> 0 -> 1 -> NULL (represents 1000)

Approach:
Technique to be used: Simulated addition with carry handling.
To add two numbers represented by linked lists, we can use a single pass approach by simulating the addition as we traverse the lists.

Steps:

  1. Initialize a dummy node to act as the head of the result list and a current pointer to keep track of the last node in the result list.
  2. Initialize a carry variable to store the carry-over during addition.
  3. Traverse both lists simultaneously, adding corresponding digits along with the carry from the previous addition.
  4. Update the carry for the next digit.
  5. If there are remaining digits in one list after the other has been fully traversed, continue adding those digits along with the carry.
  6. If there is a carry remaining after the final addition, add a new node with that carry value.
  7. Return the result list starting from the node next to the dummy node.

C++ Program to add two numbers represented by Linked Lists

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        int carry = 0;

        while (l1 != NULL || l2 != NULL || carry) {
            int sum = carry;
            if (l1 != NULL) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }

        return dummy.next;
    }
};

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

int main() {
    // Creating two linked lists: 2 -> 4 -> 3 and 5 -> 6 -> 4
    ListNode* l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    Solution sol;
    ListNode* result = sol.addTwoNumbers(l1, l2);

    // Printing the result linked list
    cout << "Result list: ";
    printList(result);

    return 0;
}

Java Program to add two numbers represented by Linked Lists

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

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

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }

        return dummy.next;
    }
    
    // Helper 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("NULL");
    }

    public static void main(String[] args) {
        // Creating two linked lists: 2 -> 4 -> 3 and 5 -> 6 -> 4
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        Solution sol = new Solution();
        ListNode result = sol.addTwoNumbers(l1, l2);

        // Printing the result linked list
        System.out.print("Result list: ");
        printList(result);
    }
}

Python Program to add two numbers represented by Linked Lists

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        current = dummy
        carry = 0
        
        while l1 or l2 or carry:
            sum = carry
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
                
            carry = sum // 10
            current.next = ListNode(sum % 10)
            current = current.next
        
        return dummy.next

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating two linked lists: 2 -> 4 -> 3 and 5 -> 6 -> 4
l1 = ListNode(2)
l1.next = ListNode(4)
l1.next.next = ListNode(3)

l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)

sol = Solution()
result = sol.addTwoNumbers(l1, l2)

# Printing the result linked list
print("Result list:", end=" ")
print_list(result)

Adding two numbers represented by linked lists can be efficiently achieved by simulating the addition with carry handling. This approach ensures that we handle the addition digit by digit, including the carry-over for each digit.

DSA

7822

412

Related Articles