在 C++ 中合并两个排序链表

Question

我正在尝试编写一个算法来合并两个排序的链表。我无法理解为什么这不能给我正确的答案。为什么答案没有早期作业的记忆，它只返回最近完成的作业。(即长度为 1 的链表(。我正在创建一个名为cur的初始节点，然后我根据l1和l2的值向其添加nexts，并且每次都执行cur.next。谢谢

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){};
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode cur;
ListNode* ans = new ListNode;
ans = &cur;
while (l1 && l2) {
if (l1->val < l2->val) {
ListNode temp(l1->val);
cur.next = &temp;
l1 = l1->next;
cur = *(cur.next);
} else {
ListNode temp(l2->val);
cur.next = &temp;
l2 = l2->next;
cur = *(cur.next);
}
}
if (l1) {
cur.next = (l1);
}
if (l2) {
cur.next = (l2);
}
return ans->next;
};

Answer 1

主要问题是您没有向前移动cur以便可以将新节点附加到列表中。就像您现在一样cur.next = &temp每次都重置next指针。此外，由于temp变量是if分支作用域的局部变量，因此当您执行cur.next = &temp时，您将next指针设置为一个对象，该对象将在每次if语句结束时消失，从而导致指针悬空。最好动态分配：

ListNode ans;
ListNode* cur = &ans;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = new ListNode(l1->val);
l1 = l1->next;
} else {
cur->next = new ListNode(l2->val);
l2 = l2->next;
}
cur = cur->next;
}
if (l1)
cur->next = l1;
else
cur->next = l2;
return ans.next;

Answer 2

让我们浏览一下if块中的代码，以尝试了解发生了什么。

ListNode temp(l1->val);
cur.next = &temp;
l1 = l1->next;
cur = *(cur.next);

第 #1 行在新分配的内存位置中创建一个名为 temp 的新 ListNode 变量。假设此内存位置的地址是 X123。在此内存位置，temp.val 存储 l1->val，temp.next 为 nullptr。

行 #2 要求将临时变量的地址存储在 cur.next 中，因此 cur.next 将在执行第 #2 行后存储 X123。

第 #3 行要求将 l1 指向 l1->next。这是在做你所期望的。

现在密切关注#4行。它没有做你认为它正在做的事情。在上面的评论中，你说：

我正在做cur=*(cur.next(，它应该向前移动cur。

但这并不完全正确。"向前移动cur"没有意义，因为cur不是指向ListNode的指针，它只是一个ListNode对象。所以行 #4 要求复制存储在内存位置 cur.next(即内存位置 X123(的对象，并将其粘贴到 cur 占用的内存位置。换句话说，它要求将临时对象复制到cur对象占用的内存位置。因此，在 #4 行执行后，cur.val 将存储 temp.val 中的任何内容(即最新的 l1->val(，cur.next 将存储 temp.next 中的任何内容(即 nullptr(。

这样做会丢失指向 temp 内存位置 X123 的指针，因为 cur.next 存储了它，现在你已经用 nullptr 覆盖了它！这就是为什么最后你有一个带有最后一个(最新(作业的cur。所有早期的赋值都会丢失，因为您在每次迭代中都会用新内容覆盖 cur 的内容。你永远不会"前进"。

解决方案是使用指针。让 cur 成为 ListNode* 指针而不是 ListNode 对象，并尝试解决问题。

希望这有帮助，欢迎来到SO。干杯！