太久没接触数据结构了，导致链表这一块的内容有点生疏了，这两天在做一道链表相关的题时出现了一点问题，在此记录一下以免之后再犯。

问题描述

题目链接

两数相加

链表定义

1
2
3
4
5
6
7
struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* headNode = nullptr;
        ListNode* pathNode = nullptr;
        int c = 0;
        while (l1 && l2)
        {
            int sum = l1->val + l2->val + c;
            c = sum / 10;
            pathNode = new ListNode(sum % 10);
            if (!headNode)
                headNode = pathNode;
            pathNode = pathNode->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1)
        {
            int sum = l1->val + c;
            c = sum / 10;
            pathNode = new ListNode(sum % 10);
            pathNode = pathNode->next;
        }
        while (l2)
        {
            int sum = l2->val + c;
            c = sum / 10;
            pathNode = new ListNode(sum % 10);
            pathNode = pathNode->next;
        }
        if (c)
        	pathNode = new ListNode(c);
        return headNode;
    }
};

代码乍一看好像没有问题，headNode在指向最初的pathNode后就没有再变更，pathNode也是在每次生成新节点后指向它的子节点，但最后测试得到的结果表明headNode为一个孤立的节点（它的子节点为空指针）。

问题解决

原因分析

原来在生成子节点的过程中，我先让pathNode指向它的子节点（此时pathNode子节点为nullptr），然后再让其指向新的节点，这样问题就出现了。

因为在pathNode子节点为nullptr的时候指向它是没有任何意义的，在随后的 pathNode = new ListNode(sum % 10);中pathNode又指向了一个动态创建的地址，这个地址与原先的pathNode根本没有任何联系，最后得到的结果只能是前一个pathNode结点的子节点仍然为nullptr。正确的做法应该是先对pathNode的子节点赋值，再执行pathNode = pathNode->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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* headNode = nullptr;
        ListNode* pathNode = nullptr;
        int c = 0;
        while (l1 && l2)
        {
            int sum = l1->val + l2->val + c;
            c = sum / 10;
            if (!headNode) {
                pathNode = new ListNode(sum % 10);
                headNode = pathNode;
            }
            else {
                pathNode->next = new ListNode(sum % 10);
                pathNode = pathNode->next;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1)
        {
            int sum = l1->val + c;
            c = sum / 10;
            pathNode->next = new ListNode(sum % 10);
            pathNode = pathNode->next;
            l1 = l1->next;
        }
        while (l2)
        {
            int sum = l2->val + c;
            c = sum / 10;
            pathNode->next = new ListNode(sum % 10);
            pathNode = pathNode->next;
            l2 = l2->next;
        }
        if(c)
            pathNode->next = new ListNode(c);
        return headNode;
    }
};