LeetCode add two numbers : explanations and solutions with Cpp/Java/Python

Challenge Description

An sample input:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Explanation

This problem tests the skills of linked list operation. Two points need to notice here:

• How to merge two linked list into one
• How to use a dummy node to simplify code logic

Merge two linked lists

It’s straightforward to iterate over two node pointers. But please notice the scenario of one linked list is longer than the other one. We need to make sure a node is valid before using it. This is error-prone for starter.

Assume that $m$ and $n$ represents the length of $l1$ and $l2$ respectively:

The time complexity: $O(max(M, N))$

The space complexity: $O(max(M, N))$

Use the dummy node

What’s dummy node?

If we don’t use dummy node, we must have a variable which pointing to the final result. If we don’t initialize it beforehand, we need to construct it during the loop. the pseudo code should be:

node* res = null
node* p = null
while(...) {
  if(res == null) {
     res = new node with val 
     p = res
  }
  .... 
}

Hence the code is a little complicated, and it’s also mixed with other logic for merging node.

The idea of dummy node is we initialize a unused node firstly, then we always keep the dummy.next to be the head node. This is good taste for linked list.

C++

class Solution {
public:
  ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode dummy(0);
    ListNode* p = &dummy;
    int carry = 0, sum;
    while(l1 || l2) {
      sum = carry;
      if(l1) sum += l1->val;
      if(l2) sum += l2->val;
      if(sum >= 10) {
        carry = sum / 10;
        sum %= 10;
      } else carry = 0;
      p->next = new ListNode(sum);
      p = p->next;
      if(l1) l1 = l1->next;
      if(l2) l2 = l2->next;
    }
    if(carry)
      p->next = new ListNode(carry);
    return dummy.next;
  }
};

Java

Notice this Java version don’t test the sum >= 10, I keep it in C++ version for a little better time performance.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

Python

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

      if carry == 1:
          resList.next = ListNode(carry)

      return dummy.next

Preparing for an interview? Check out this!