算法篇--链表求和_链表—累加和

问题描述

给两个链表，每个链表为一个整数的倒序，如下：

1 - 2 - 3
4 -5 - 7- 9
两个数字的结果：
321+9754= 10075

那么！ 请得到 链表的结果为 5 - 7 - 0 - 0 - 1

思考

思路总结： 两个链表肯定有一个最长的（等于情况取哪个都行），所以两个链表相加时候就用 短的限制循环边界，
跳出循环后则 遍历长的 相加
几点注意：

• 1 每两个节点相加时，也要加 上一次的进位信息
• 2 当长的链表遍历后，注意进位信息的处理

代码

public class SumLink extends BaseLink {


  

    public static Node<Integer> sumLinkWihtNode(Node<Integer> head1, Node<Integer> head2) {
        if (head1 == null || head2 == null) {
            return head1 != null ? head1 : head2;
        }
        int head1Len = lenLink(head1);
        int head2Len = lenLink(head2);
        Node<Integer> curL = head1Len >= head2Len ? head1 : head2;
        Node<Integer> curS = curL != head1 ? head1 : head2;
        int carry = 0;

        Node<Integer> realhead = curL;
        Node<Integer> lastNode = curL;

        while (curS != null) {
            int tempSum = curL.v + curS.v + carry;
            curL.v = tempSum % 10;
            carry = tempSum / 10;

            lastNode = curL;

            curL = curL.next;
            curS = curS.next;
        }

        while (curL != null) {
            int tempSum = curL.v + carry;
            curL.v = tempSum % 10;
            carry = tempSum / 10;

            lastNode = curL;

            curL = curL.next;

        }
        if(carry != 0){
            lastNode.next = new Node<>(1);
        }

        return realhead;
    }

    private static int lenLink(Node head1) {

        int ans = 0;
        while (head1 != null) {
            head1 = head1.next;
            ans++;
        }
        return ans;
    }


    public static void main(String[] args) {
        var head1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);


        head1.next = node2;
        node2.next = node3;


        Node head2 = new Node(4);
        Node node52 = new Node(5);
        Node node62 = new Node(7);
        Node node72 = new Node(9);


        head2.next = node52;
        node52.next = node62;
        node62.next = node72;


        Node<Integer> node = sumLinkWihtNode(head1, head2);
        while (node!=null){
            System.out.println(node.v);
            node = node.next;
        }
    }

}

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88