LeetCode: Add Two Numbers

LeetCode: Add Two Numbers 1

Last Updated on

\(\)

Question

https://leetcode.com/problems/add-two-numbers/

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 contain a single digit. Add the two numbers and return it as a linked list.

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

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

Explanation

This problem test the skills of linked list node operation. There are two points here:

  1. Merge two link list into one
  2. Use the dummy node to simplify code logic

Merge two link list

It’s straightforward to iterate the two link node pointer, notice the condition when one link list is longer than another one, so we need to test whenever we need to fetch information from a list node.

That’s error-prone point 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?

We have a variable point to the final result, if we don’t initialize it, we need to construct it during the loop. the pseudocode 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 node merge.

The idea of ‘dummy node’ is we initialize a unused node first, 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:
      resHead = 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 resHead.next