445. Add Two Numbers II.md

445. Add Two Numbers II

---

leetcode Daily Challenge on November 7th, 2020.

---

Difficulty : Medium

Related Topics : Linked List

---

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

Follow up:

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

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
Explanation: 7243 + 564 = 7807.

---

Solution

• mine
  • Java
    • Runtime: 2 ms, faster than 98.96%, Memory Usage: 39.7 MB, less than 9.37% of Java online submissions

      // O(N)time
      // O(N)space
      public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          l1 = reverse(l1);
          l2 = reverse(l2);
          int t = 0;
          ListNode res = new ListNode(0);
          ListNode temp = res;
          while (l1 != null || l2 != null) {
              int num = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + t;
              t = num / 10;
              temp.next = new ListNode(num % 10);
              temp = temp.next;
              l1 = l1 != null ? l1.next : null;
              l2 = l2 != null ? l2.next : null;
          }
          if (t != 0) {
              temp.next = new ListNode(t);
          }
          return reverse(res.next);
      }
      
      ListNode reverse(ListNode node) {
          ListNode res = null;
          while (node != null) {
              ListNode t = node.next;
              node.next = res;
              res = node;
              node = t;
          }
          return res;
      }
      

---

• the most votes

• Runtime: 3 ms, faster than 65.69%, Memory Usage: 39.9 MB, less than 9.37% of Java online submissions

  // O(N)time
  // O(N)space
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      Stack<Integer> s1 = new Stack<Integer>();
      Stack<Integer> s2 = new Stack<Integer>();
  
      while(l1 != null) {
          s1.push(l1.val);
          l1 = l1.next;
      };
      while(l2 != null) {
          s2.push(l2.val);
          l2 = l2.next;
      }
  
      int sum = 0;
      ListNode list = new ListNode(0);
      while (!s1.empty() || !s2.empty()) {
          if (!s1.empty()) sum += s1.pop();
          if (!s2.empty()) sum += s2.pop();
          list.val = sum % 10;
          ListNode head = new ListNode(sum / 10);
          head.next = list;
          list = head;
          sum /= 10;
      }
  
      return list.val == 0 ? list.next : list;
  }
  

---