Java每日一题——＞ 剑指 Offer II 025. 链表中的两数相加_leetcode java 25 两数相加ii

这是LeetCode上的 [025，链表中的两数相加]，难度为 [中等]

题目

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

示例

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
1
2

思路分析

通常，两个整数相加都是先加个位数，再加十位数，以此类推。在做加法时还需要注意进位，如果两个整数的个位数相加超过10，就会往十位数产生一个进位，在下一步做十位数相加时就要把这个进位加进去

综上，我们需要从链表尾部开始遍历加起（个位数在尾结点），由于链表只能从头结点开始遍历，因此有两种方法可以实现（反转方法，栈方法）

题解1(栈方法）

在遍历链表过程中，把结点压入栈（后进先出）。所以出栈的第一个结点为个位数，出栈的最后一个结点为最高位

步骤

1. 定义两个栈，存放两个链表的结点
2. 遍历两链表，遍历过程中依次把结点压入栈
3. 定义一个sumNode结点，存放结果链表的头结点，初始为null
4. 定义一个变量carry，初始为0，存放两个数的某位数相加后的进位
5. 遍历，把两个栈同时出栈，若两链表的长度相等，则两栈同时为空时结束。若两链表长度不相等，则长的栈为空时结束。遍历过程中执行如下操作
   • 声明一个变量sum存放两个数的某位数相加的值
   • 判断栈是否空，若为空，让当前结点的值为0。因为如果两链表长度不相等，短的链表的栈可能为空。否则弹出两个栈的结点
   • 让两个结点的值相加，并且加上进位值carry，结果赋值给sum
   • 判断sum的值是否>=10，若>=10,则产生进位，让carry等于1，并且让sum=sum - 10，否则让carry等于0，不改变sum的值
   • 定义一个新结点newNode，值为sum的值
   • 让新结点指向sumNode(头结点），新结点成为头结点
   • 重置sumNode为头结点，把新结点的值赋给sumNode
6. 判断carry的值是否大于0（当两链表长度相等时，最高位相加可能会进位），若大于，创建一个新结点，值为carry，并且让新结点指向sumNode成为头结点，之后重置sumNode为头结点，把新结点的值赋给sumNode

代码实现

class Solution {
       public ListNode addTwoNumbers(ListNode headA, ListNode headB) {
        // 定义两个栈，存放两个链表的结点
        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();
        // 遍历两链表，遍历过程中依次把结点压入栈
        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }
        // 定义一个sumNode结点，存放结果链表的头结点，初始为null
        ListNode sumNode = null;
        // 定义一个变量carry，初始为0，存放两个数的某位数相加后的进位
        int carry = 0;
        /*遍历，把两个栈同时出栈，若两链表的长度相等，则两栈同时为空时结束
          若两链表长度不相等，则长的栈为空时结束*/
        while (!stackA.isEmpty() || !stackB.isEmpty()) {
            /* 声明一个变量sum存放两个数的某位数相加的值. 在相加之前判断栈是否空，
               若为空，让当前结点的值为0。因为如果两链表长度不相等，短的链表的栈可能为空。
               否则弹出两个栈的结点*/
            int sum = (stackA.isEmpty() ? 0 : stackA.pop().val) + (stackB.isEmpty() ? 0 : stackB.pop().val) + carry;
            // 判断sum的值是否>=10，若>=10,则产生进位，让carry等于1
            carry = sum >= 10 ? 1 : 0;
            // 判断sum的值是否>=10，若>=10,让让sum=sum - 10,否则不改变sum的值
            sum = sum >= 10 ? sum - 10 : sum;
            // 定义一个新结点newNode，值为sum的值
            ListNode newNode = new ListNode(sum);
            // 让新结点指向sumNode(头结点），新结点成为头结点
            newNode.next = sumNode;
            // 重置sumNode为头结点，把新结点的值赋给sumNode
            sumNode = newNode;
        }
        /* 判断carry的值是否大于0（当两链表长度相等时，最高位相加可能会进位），
            若大于，创建一个新结点，值为carry
            并且让新结点指向sumNode成为头结点，之后重置sumNode为头结点，把新结点的值赋给sumNode*/
        if (carry > 0) {
            ListNode newNode = new ListNode(carry);
            newNode.next = sumNode;
            sumNode = newNode;
        }
        // 返回结果链表的头结点
        return sumNode;
    }
}
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

结点类

public class ListNode<T> {

    T val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(T val) {
        this.val = val;
    }

    public ListNode(T val, ListNode next) {
        this.next = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试代码

public class Test {

    @org.junit.Test
    public void test1() {
        ListNode headA = new ListNode(9);
        ListNode one = new ListNode(8);
        ListNode two = new ListNode(4);
        headA.next = one;
        one.next = two;

        ListNode headB = new ListNode(1);
        ListNode first = new ListNode(8);
        headB.next = first;

        ListNode sumHead = new Solution().addTwoNumbers1(headA, headB);

        System.out.print("984 + 18 = ");
        while (sumHead != null) {
            System.out.print(sumHead.val);
            sumHead = sumHead.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

假设两链表长度为n,m

时间复杂度：

在最初遍历两个链表压栈时，时间复杂度为O(n+m)，在同时遍历两个栈时，时间复杂度为O(n)或O(m)，故总的时间复杂度为O(n+m) + O(n)或O(m) = O(n+m)

空间复杂度：

需要声明两个栈来存放两个链表结点，故空间复杂度为O(n+m)

题解2(反转链表）

反转之后的链表的头结点表示个位数，尾结点表示最高位数，此时从两个链表的头结点开始相加，就相当于从整数的个位数开始相加，反转链表已在以往文章给出，这里不再阐述

步骤

1. 反转两个链表

2. 定义一个sumNode结点，存放结果链表的头结点，初始为null

3. 定义一个变量carry，初始为0，存放两个数的某位数相加后的进位

4. 同时遍历两个链表，若两链表的长度相等，则同时遍历完两链表时结束。若两链表长度不相等，则遍历完长的链表时结束。遍历过程中执行如下操作

   • 声明一个变量sum存放两个数的某位数相加的值

   • 判断当前结点是否为null，若为null，让为null的结点的值为0。因为如果两链表长度不相等，短的链表的当前结点可能为null。

   • 让两个链表的当前结点的值相加，并且加上进位值carry，结果赋值给sum

   • 判断sum的值是否>=10，若>=10,则产生进位，让carry等于1，并且让sum=sum - 10，否则让carry等于0，不改变sum的值

   • 定义一个新结点newNode，值为sum的值

   • 让新结点指向sumNode(头结点），新结点成为头结点

   • 重置sumNode为头结点，把新结点的值赋给sumNode

   • 重置当前结点，把当前结点的下一个结点作为当前结点，实现遍历

5. 判断carry的值是否大于0（当两链表长度相等时，最高位相加可能会进位），若大于，创建一个新结点，值为carry，并且让新结点指向sumNode成为头结点，之后重置sumNode为头结点，把新结点的值赋给sumNode

代码实现

class Solution {
       public ListNode addTwoNumbers(ListNode headA, ListNode headB) {
        // 反转两个链表
        headA = reverseList(headA);
        headB = reverseList(headB);
        // 把反转后的每一个位相加，得到的结果就是两个的和的结果
        ListNode sumReverse = addReverse(headA, headB);
        // 把结果返回
        return sumReverse;
    }

    // 反转链表方法
    public ListNode reverseList(ListNode headA) {
        ListNode preNode = null;
        ListNode currNode = headA;
        while (currNode != null) {
            ListNode nextNode = currNode.next;
            currNode.next = preNode;
            preNode = currNode;
            currNode = nextNode;
        }
        return preNode;
    }

    public ListNode addReverse(ListNode headA, ListNode headB) {
        // 定义一个sumNode结点，存放结果链表的头结点，初始为null
        ListNode sumNode = null;
        // 定义一个sumNode结点，存放结果链表的头结点，初始为null
        int carry = 0;
        // 同时遍历两个链表，若两链表的长度相等，则遍历完链表时结束。若两链表长度不相等，则遍历完长的链表时结束
        while (headA != null || headB != null) {
            /* 声明一个变量sum存放两个数的某位数相加的值,并且加上carry。 在相加之前先判断当前结点是否为null
               若为null，让为null的结点的值为0。因为如果两链表长度不相等，短的链表的当前结点为null。*/
            int sum = (headA == null ? 0 :headA.val) + (headB == null ? 0 : headB.val) + carry;
            // 判断sum的值是否>=10，若>=10,则产生进位，让carry等于1
            carry = sum >= 10 ? 1 : 0;
            // 判断sum的值是否>=10，若>=10,让让sum=sum - 10,否则不改变sum的值
            sum = sum >= 10 ? sum - 10 : sum;
            // 定义一个新结点newNode，值为sum的值
            ListNode newNode = new ListNode(sum);
            // 让新结点指向sumNode(头结点），新结点成为头结点
            newNode.next = sumNode;
            // 重置sumNode为头结点，把新结点的值赋给sumNode
            sumNode = newNode;
            // 重置当前结点，把当前结点的下一个结点作为当前结点，实现遍历
            headA = headA == null ? null :headA.next;
            headB = headB == null ? null :headB.next;
        }
        /* 判断carry的值是否大于0（当两链表长度相等时，最高位相加可能会进位），
            若大于，创建一个新结点，值为carry
            并且让新结点指向sumNode成为头结点，之后重置sumNode为头结点，把新结点的值赋给sumNode*/
        if (carry > 0) {
            ListNode newNode = new ListNode(carry);
            newNode.next = sumNode;
            sumNode = newNode;
        }
        // 返回结果链表的头结点
        return sumNode;
    }
}
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
54
55
56
57
58
59
60

复杂度分析

假设两链表长度位n,m

时间复杂度:

在最初遍历反转两个链表时，时间复杂度位O(n),O(m)，在算两个数的和时，需要同时遍历两个链表，故时间复杂度位为O(n)或O(m)，则总时间复杂度为O(n) + O(m) + O(n)或O(m) = O(n)

空间复杂度：

只声明了几个固定的结点，故空间复杂度为O（1）；