2. Add Two Numbers (Linked List)

LeetCode

My Wrong Sol: Read + Add

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
47
48
49
50
51
52
53
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int num1 = 0;
        int num2 = 0;
        int mul = 1;
        
        while(l1 != null){
            num1 = num1 + mul * l1.val;
            mul = mul * 10;
            l1 = l1.next;
        }

        mul = 1;

        while(l2 != null){
            num2 = num2 + mul * l2.val;
            mul = mul * 10;
            l2 = l2.next;
        }

        int sum = num1 + num2;


        int len = String.valueOf(sum).length();

        String str = String.valueOf(sum);


        ListNode result = new ListNode(); // dummy
        ListNode current = result;

        while (len > 0) {
            ListNode next = new ListNode(str.charAt(str.length() - 1) - '0');  // 创建节点并赋值
            current.next = next;  // 接到链表上
            current = next;       // 移动指针
            str = str.substring(0, str.length() - 1);
            len--;
        }


        return result.next;
    }
}

Failed: cannot process big numbers, out of int range.

Adder

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while(l1 != null || l2 != null || carry > 0){
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;

            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummy.next;
    }
}

Remarks:

  1. How to new a object in Java?

    ListNode dummy = new ListNode(0);

  2. Use carry

  3. Set a dummy node (the first one) and skip it.