題目：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:

• 鏈表頭結(jié)點(diǎn) :: ListNode
• 另一個鏈表頭結(jié)點(diǎn) :: ListNode

Output:

• 相加后鏈表頭結(jié)點(diǎn) :: ListNode

Intuition:

這題就很直接的每個元素相加就好，但是tricky的地方在于如何處理進(jìn)位炒辉。很顯然我們需要一個變量來存儲當(dāng)前位的進(jìn)位狀況然后在下一位的時候添加上豪墅。

Code:

TC: (n) SC: (1)

public ListNode addTwoNum(ListNode l1, ListNode l2){
  ListNode dummy = new ListNode(-1);
  ListNode p = dummy;
  ListNode p1 = l1;
  ListNode p2 = l2;
  int sum = 0;
  int carry = 0;

  while (p1 != null && p2 != null){
    if (p1 != null){
      sum += p1.val;
      p1 = p1.next;
    }
    
    if (p2 != null){
      sum += p2.val;
      p2 = p2.next;
    }
    //save carry for next round addition
    carry = sum / 10;
    p.next = new ListNode( sum % 10);
    p = p.next;
    sum /= 10;
  }
  if(carry == 1) p.next = new ListNode(1);
  return dummy.next;
}

題目：Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the list is not allowed.

Input:

• 鏈表頭結(jié)點(diǎn) :: ListNode
• 另一個鏈表頭結(jié)點(diǎn) :: ListNode

Output:

• 相加后鏈表頭結(jié)點(diǎn) :: ListNode

Intuition:

跟第一題不同的地方就在于這回鏈表表示的數(shù)字跟我們默認(rèn)的數(shù)字是一樣的，最小位在左邊辆脸。需要解決的問題其實(shí)還是進(jìn)位但校，不過我們得倒著加螃诅，即把左邊的高位數(shù)的數(shù)先存著啡氢，低位數(shù)加完后再來加高位數(shù)。是不是聽著挺耳熟术裸？這不就是先進(jìn)后出嘛倘是？所以我們需要一個stack。

Code:

TC: (n) SC: (n)

public ListNode addTwoNum(ListNode l1, ListNode l2){
  Deque<Integer> stk1 = new ArrayDeque<>();
  ListNode dummy = new ListNode(-1);
  ListNode p = dummy;
  ListNode p1 = l1;
  ListNode p2 = l2;
  int sum = 0;
  int carry = 0;
  //use stack to reverse order
  while (p1 != null && p2 != null){
    if (p1 != null){
      stk1.push(p1.val);
      p1 = p1.next;
    }
    
    if (p2 != null){
      stk2.push(p2.val);
      p2 = p2.next;
    }
  }
    
  while(!stk1.isEmpty() || !stk2.isEmpty()){
    //save carry for next round addition
    if (!stk1.isEmpty()){
      sum += stk1.pop()
    }
    
    if (!stk2.isEmpty()){
      sum += stk1.pop()
    }
    carry = sum / 10;
    ListNode cur = new ListNode(carry);
    cur.next = ListNode( sum % 10);
    cur =
    p = p.next;
    sum /= 10;
  }
  return dummy.next;
}

Reference

https://leetcode.com/problems/add-two-numbers/description/
https://leetcode.com/problems/add-two-numbers-ii/discuss/