剑指 Offer II 025. 链表中的两数相加

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

可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：

img

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

示例2：

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

示例3：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

提示：

  • 链表的长度范围为 [1, 100]
  • 0 <= node.val <= 9
  • 输入数据保证链表代表的数字无前导 0

思路：

按照平常加法的思路都是从个位相加，有进位则进到十位然后十位相加，以此类推。

对于链表也可以如此操作，但是我们没法对单链表从尾结点进行此种操作，所以需要对链表进行反转，然后相加即可。

步骤：

  1. 反转两个链表
  2. 将短链表后面进行补充值为0的节点至两链表长度相同
  3. 链表相加，针对进位需要设置进位标志位
  4. 最后一个节点需要单独判断，因为它的大小关乎着是否需要新增节点
  5. 将加和完的链表进行反转

代码实现：

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
89
90
91
92
93
94
95
96
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
    //1.反转两链表
    head1 = reverse(head1);
    head2 = reverse(head2);
    //2.链表补零
    addZero(head1,head2);

    //3.设置进位，链表相加
    int carry = 0;
    //当前两节点值之和
    int curSum = 0;
    //标识头结点，因为head1和head2要用于遍历节点
    //用head1标识最后相加完之后的链表
    ListNode head = head1;

    //只遍历到倒数第二位
    while(head1.next != null){
        //相加时要加上进位
        curSum = head1.val + head2.val + carry;
        //每次进位后要置零
        if(carry == 1){
            carry = 0;
        }
        //当前两个值之和大于等于时，有进位
        if(curSum >= 10){
            head1.val = curSum%10;
            carry =1;
        }else{
            head1.val = curSum;
        }
        head1 = head1.next;
        head2 = head2.next;

    }
    //最后一位的相加要单独计算时候大于10，如果大于需要添加节点

    curSum = head1.val + head2.val + carry;
    //有进位，新添加节点
    if(curSum >= 10){
        head1.val = curSum%10;
        head1.next = new ListNode(1);
        head1.next.next = null;
    }else{
        head1.val = curSum;
    }
    //4.翻转链表，将链表返回
    return reverse(head);


}


void addZero(ListNode head1,ListNode head2){
    //先遍历到短链表结束的地方
    while(head1.next!= null && head2.next != null){
        head1 = head1.next;
        head2 = head2.next;
    }
    //将短链表进行补零操作
    if(head1.next != null){
        while(head1.next != null){
            head2.next = new ListNode(0);
            head2.next.next = null;
            head2 = head2.next;
            head1 = head1.next;
        }
    }
    if(head2.next != null){
        while(head2.next != null){
            head1.next = new ListNode(0);
            head1.next.next = null;
            head1 = head1.next;
            head2 = head2.next;
        }
    }



}


//链表反转
ListNode reverse(ListNode head){
    ListNode  cur = head;
    ListNode pre = null;
    ListNode temp = null;

    while(cur != null){
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;

    }
    return pre;
}