AcWing 36. 合并两个排序的链表
原题链接
简单
作者:
我要出去乱说
,
2021-02-06 20:10:18
,
所有人可见
,
阅读 1031
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
auto d = new ListNode(-1), p = d; //d是头指针,p是尾指针
while (l1 && l2)
if (l1->val < l2->val) //l1当前节点的值小,则把l1这个节点放到链表尾部
{
p = p->next = l1; //我们一直让p指向下一个节点
l1 = l1->next; //注意p不是生来就是尾指针,是我们的做法让它变成尾指针
}
else
{
p = p->next = l2;
l2 = l2->next;
}
if (l1) p->next = l1; //这不是单个赋值,是把整个剩下的l1链表接到p的后面去
if (l2) p->next = l2;
return d->next; //返回头指针,不能返回d,因为d是从-1开始的
}
};
妙,讲解清晰
请问d->next初始不是为0吗?什么时候改变指向第一个位置呢?
auto d = new ListNode(-1)
的意思是调用单链表类的构造函数创建了一个头结点为-1
的单链表,其实这个值是’-1’或是‘0’都无所谓的,因为根本不会用到这个值。d指向的是-1这个值,整个过程中我们不会改变d的指向,而是用了一个临时指针p来操作链表合并。最后返回d->next
指向的才是真正链表的起始节点.