Add Two Numbers II

Leetcode 455.

version 1 Without Modify the original Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      Stack<Integer> l1Stack = buildStack(l1);
      Stack<Integer> l2Stack = buildStack(l2);
      int carry = 0; 
      int current = 0; 
      ListNode newList = new ListNode(-1);
      while(!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0){
        int a = l1Stack.isEmpty() ? 0 : l1Stack.pop();
        int b = l2Stack.isEmpty() ? 0 : l2Stack.pop();
        current = (carry + a + b) % 10;
        ListNode node = new ListNode(current);
        node.next = newList.next; 
        newList.next = node; 
        carry = (carry + a + b) / 10;
      }
      return newList.next;
    }
    public Stack<Integer> buildStack(ListNode l){
       Stack<Integer> stack = new Stack<>();
       while(l != null){
           stack.push(l.val);
           l = l.next;
       }
      return stack; 
    }

}

version 2 Modify the original Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newL1 = reverseLinkedList(l1);
        ListNode newL2 = reverseLinkedList(l2);
        int carry = 0;
        int current = 0; 
        ListNode newList = new ListNode(-1);
        ListNode temp = newList;
        while(newL1 != null || newL2 != null){
           int a = newL1 == null ? 0 : newL1.val;
           int b = newL2 == null ? 0 : newL2.val;
           current = (a+b + carry) % 10;
           temp.next = new ListNode(current); 
           carry = (a+b + carry) / 10;
           temp = temp.next;
           if(newL1 != null)
            newL1 = newL1.next;
           if(newL2 != null)
            newL2 = newL2.next; 
        }
        //case [5] [5] --> carry = 1 
        if(carry == 1){
           temp.next = new ListNode(carry);
           temp = temp.next;
        }          
        temp.next = null;
        ListNode result = reverseLinkedList(newList.next);
        return result;
    }
    public ListNode reverseLinkedList(ListNode input){
       if(input == null || input.next == null)
          return input;
       ListNode temp = reverseLinkedList(input.next);
       input.next.next = input; 
       input.next = null; 
       return temp; 
    }
}