445 Add Two Numbers II

Search…

445. Add Two Numbers II​
1. Question
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:
1
Input: (7 -> 2 -> 4 ->3) + (5 -> 6 -> 4)
2
​
3
Output: 7 -> 8 -> 0 ->7
Copied!
2. Implementation
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */
9
class Solution {
10
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
11
        ListNode p1 = reverse(l1);
12
        ListNode p2 = reverse(l2);
13
​
14
        int sum = 0;
15
        ListNode dummy = new ListNode(0);
16
        ListNode curNode = dummy;
17
​
18
        while (p1 != null || p2 != null) {
19
            if (p1 != null) {
20
                sum += p1.val;
21
                p1 = p1.next;
22
            }
23
​
24
            if (p2 != null) {
25
                sum += p2.val;
26
                p2 = p2.next;
27
            }
28
​
29
            curNode.next = new ListNode(sum % 10);
30
            sum /= 10;
31
            curNode = curNode.next;
32
        }
33
​
34
        if (sum != 0) {
35
            curNode.next = new ListNode(sum);
36
        }
37
​
38
        return reverse(dummy.next);
39
    }
40
​
41
    public ListNode reverse (ListNode head) {
42
        ListNode curNode = head, preNode = null, nextNode = null;
43
​
44
        while (curNode != null) {
45
            nextNode = curNode.next;
46
            curNode.next = preNode;
47
            preNode = curNode;
48
            curNode = nextNode;
49
        }
50
        return preNode;
51
    }
52
}
Copied!
3. Time & Space Complexity
时间复杂度O(m + n), m是第一个list的长度, n是第二个list的长度，空间复杂度O(1)

379 Design Phone Directory

725 Split Linked List in Parts

Last modified 2yr ago

Copy link

Contents

445. Add Two Numbers II

1. Question

2. Implementation

3. Time & Space Complexity

445. Add Two Numbers II​

1. Question

2. Implementation

3. Time & Space Complexity

445. Add Two Numbers II