Skip to content

2. Add Two Numbers

Medium

Description

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.

Example 1:

Example_1_img

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

Example 2:

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

Example 3:

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

Constraints:

  • 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.

Solutions

Approach 1: Simulation

Time complexity: \(O(max((M,N)))\)

Space complexity: \(O(1)\)

Notes

We traverse two linked lists and at the same time, and use the variable carry to indicate whether there is a carry.

Each time we traverse, we take out the current bit of the corresponding linked list, calculate the sum with the carry carry, and then update the value of the carry. Then we add the current bit to the answer linked list.

If both linked lists are traversed, and the carry is 0, the traversal ends.

Finally, we return the head node of the answer linked list.

The time complexity is O(max((M,N))), where M and N are the lengths of the two linked lists. We need to traverse the entire position of the two linked lists, and each position only needs O(1) time. Ignoring the space consumption of the answer, the space complexity is O(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = dummy
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry+=l1.val
                l1 = l1.next
            if l2:
                carry+=l2.val
                l2 = l2.next
            curr.next = ListNode(carry%10)
            carry = carry//10
            curr = curr.next
        return dummy.next

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    }
}

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

    }
};

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
}

impl Solution {
    pub fn add_two_numbers(
    mut l1: Option<Box<ListNode>>,
    mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {

    }
}

/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {

}

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
    }
}

class Solution {
    /**
    * @param ListNode $l1
    * @param ListNode $l2
    * @return ListNode
    */
    function addTwoNumbers($l1, $l2) {
    }
}

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {

    }
}

# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)

end