Add Two Numbers Medium ​

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

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

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Input: l1 = [0], l2 = [0]
Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Solution ​

def addTwoNumbers(l1, l2):
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0

    while l1 or l2 or carry:
        sum_val = carry
        if l1:
            sum_val += l1.val
            l1 = l1.next
        if l2:
            sum_val += l2.val
            l2 = l2.next

        carry = sum_val // 10
        current.next = ListNode(sum_val % 10)
        current = current.next

    return dummy_head.next

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode current = dummyHead;
    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 dummyHead.next;
}

function addTwoNumbers(l1, l2) {
    const dummyHead = new ListNode(0);
    let current = dummyHead;
    let carry = 0;

    while (l1 || l2 || carry) {
        let sum = carry;
        if (l1) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2) {
            sum += l2.val;
            l2 = l2.next;
        }

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

    return dummyHead.next;
}

Notes ​

In this problem, we are given two linked lists representing non-negative integers, where each node contains a single digit, and the digits are stored in reverse order. Our goal is to add the two numbers and return the sum as a new linked list.

Definition of ListNode: ​

Before we proceed with the solutions, we'll define the ListNode class in all three languages to represent the nodes of the linked list.

class ListNode:

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

    self.val = val


self.next = next

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

Solution Explanation: ​

We'll traverse both linked lists simultaneously, summing the corresponding digits and handling carry if present. The sum of two digits can be greater than 9, in which case we need to carry the extra digit to the next node.

We'll initialize a dummy node to keep track of the head of the result linked list and two pointers to traverse the input linked lists. As we iterate through the lists, we'll add the values of the nodes and the carry (if any) to compute the sum at the current position.

Time Complexity: ​

The time complexity of the solution is O(max(m, n)), where m and n are the lengths of the two input linked lists. We need to traverse both lists to calculate the sum, and the length of the resulting linked list is at most max(m, n) + 1.

Space Complexity: ​

The space complexity of the solution is O(max(m, n)). It's because we create a new linked list to store the result, and the length of the resulting linked list is at most max(m, n) + 1, where m and n are the lengths of the input linked lists. Additionally, we use a constant amount of extra space for variables current and carry.