程序接受两个排序的链表,并通过合并这些链表返回一个链表。我也写了考虑边缘情况的逻辑,但是输出没有到来。我认为问题在于第三个链表的形成。我无法形成第三个链接列表。
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *l3 = new ListNode(0);
ListNode *head = l3;
ListNode *temp = new ListNode();
if (!l1 && !l2) {
return l1;
} else if (!l1) {
return l2;
} else if (!l2) {
return l1;
} else if (l1->val <= l2->val) {
l3->val = l1->val;
l1 = l1->next;
} else {
l3->val = l2->val;
l2 = l2->next;
}
while (l1->next || l2->next) {
print(head);
print(l1);
print(l2);
if (l1->val <= l2->val) {
temp->val = l1->val;
l1 = l1->next;
} else {
temp->val = l2->val;
l2 = l2->next;
}
print(temp);
//l3 = l3->next;
l3->next = temp;
l3 = l3->next;
}
return head;
}
};
您的核心问题在于,您没有为新列表中的每个项目分配新节点:
您从l3开始,它是代表合并列表开始的新ListNode,并将l3->val
设置为适当的起始值(l1->val
和l2->val
的最小值)。稍后,您将执行与temp
类似的操作,评估列表的“当前”节点(现在由l1和l2指向),并将temp->val
设置为两者中的最小值。 问题出在,因为l1,l2,l3和temp都是ListNodes的pointers。您反复设置l3-> next以指向同一块内存(由temp指向),并且在每次循环迭代时都覆盖基础值成员。我的建议是将temp的工作视为“移交”它指向的ListNode(成为l3->next
)并更改为指向新的内存以容纳新的ListNode(用于下一次迭代),或者更好通过从l1或l2中提取min value并执行简单的l3->next = new ListNode(min_val)
来完全消除温度。使用l1,l2和l3确切地指向单独的内存块,可能会有助于绘制一个内存图,这样您就可以移动箭头并捕获更多边缘情况。
其他一些可能会使您绊倒的事情:
1)考虑您的循环条件-您已设置(循环之前和循环中的)l1 = l1->next
或l2 = l2->next
,然后继续在循环条件中引用该new值的next
成员而不检查新值本身是否为null。当您到达一个列表的末尾,但没有另一个列表的末尾时,此陷阱(空取消引用)也可能影响检查val成员。
2]起始l3->val
为0,通常不建议使用任意数字。这将是整合的好时机,在检查l1和l2都不为空之后,类似ListNode* l3 = new ListNode(min(l1->val, l2->val))
。
3)您的第一个条件没有用,因为(如果我假设如果两个列表都为空,则正确地返回null)一个列表为null只是意味着返回另一个列表是正确的,无论如何通过以下两个条件发生。
我希望有帮助!
如果目标是合并列表,则不应分配新节点,而只需更改next
成员以形成单个有序列表即可。有2个阶段:
要在合并列表的末尾链接元素,请保留指向最后一个节点的指针。
这里是修改后的版本:
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *l3 = NULL;
ListNode *head = NULL;
ListNode *n;
while (l1 && l2) {
if (l1->val <= l2->val) {
n = l1;
l1 = l1->next;
} else {
n = l2;
l2 = l2->next;
}
if (l3) {
l3 = l3->next = n;
} else {
l3 = head = n;
}
}
if (l1) {
n = l1;
} else {
n = l2;
}
if (l3) {
l3->next = n;
} else {
head = n;
}
return head;
}
};
一旦掌握了双指针,就可以改进此代码并删除头节点的测试:
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = NULL;
ListNode **nextp = &head;
while (l1 && l2) {
if (l1->val <= l2->val) {
*nextp = l1;
nextp = &l1->next;
l1 = l1->next;
} else {
*nextp = l2;
nextp = &l2->next;
l2 = l2->next;
}
}
*nextp = l1 ? l1 : l2;
return head;
}
};