Add Two Numbers

发表于 | 更新于 | 分类于

给出两个非空的有向链表代表两个非负整数
整数中每个数字以倒序形式存储在有向链表中
将两链表相加并返回相加结果的链表
例子：
输入：(2->4->3)+(5->6->4)
输出：7->0->8
含义：243+564=708

方法一：使用递归

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private int remainder;

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        remainder = 0;
        ListNode sumN = sumNode(l1, l2);

        return sumN;
    }

    private ListNode sumNode(ListNode l1, ListNode l2){
        int v1 = 0;
        int v2 = 0;
        if(l1 != null) v1 = l1.val;
        if(l2 != null) v2 = l2.val;
        int sum = v1 + v2 + remainder;
        if(sum > 9){
            remainder = sum / 10;
            sum = sum % 10;
        }else{
            remainder = 0;
        }
        ListNode sumNd = new ListNode(sum);
        if((l1 != null && l1.next != null) || (l2 != null && l2.next != null)){
            if(l1 == null || l1.next == null){
                sumNd.next = sumNode(null, l2.next);
            }else if(l2 == null || l2.next == null){
                sumNd.next = sumNode(l1.next, null);  
            }else{
                sumNd.next = sumNode(l1.next, l2.next);
            }
        }else if(remainder != 0){
            sumNd.next = new ListNode(remainder);
        }
        return sumNd;
    }
}

复杂度分析：
时间复杂度：$O(max(m,n))$
空间复杂度：$O(max(m,n))$

方法二：使用while循环

算法：

  1. 初始化返回链表的初始节点（初始节点为空）；
  2. 将余数carry初始化为0；
  3. 定义p、q分别为链表l1和l2的当前节点；
  4. 循环l1和l2直到二者均为空；
  5. 定义x为节点p的值，如果节点p为当前链表结尾，将其设为0；定义y为节点q的值，如果节点q为当前链表结尾，将其设为0；
  6. 令sum = x + y + carry，则carry = sum / 10；
  7. 初始化一个新的节点，其val为sum % 10，将其设为当前节点的next节点；
  8. 更新p、q为l1、l2的下一节点；
  9. 循环结束后如果carry大于0，则将其作为一个新节点加入到返回链表的最后；
  10. 返回初始节点的下一个节点。
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
/**
 * 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 dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

复杂度分析：
时间复杂度：$O(max(m,n))$
空间复杂度：$O(max(m,n))$