c/c++补完计划(七): 哨兵节点
c/c++补完计划(七): 哨兵节点
sean_yang
发布于 2020-08-13 11:46:07
发布于 2020-08-13 11:46:07
前言
解决链表问题, 经常会用一个空的节点进行辅助.
合并两个排序的链表
可以先考虑递归, 新建一个节点, 然后选择两个链表里面小的, 链到新建的节点. 之后移动被选择的链表, 递归这个问题.
ListNode *Merge(ListNode *pHead1, ListNode *pHead2) {
if (pHead1 == nullptr) {
return pHead2;
}
if (pHead2 == nullptr) {
return pHead1;
}
ListNode *merge;
if (pHead1->val < pHead2->val) {
merge = pHead1;
merge->next = Merge(pHead1->next, pHead2);
} else {
merge = pHead2;
merge->next = Merge(pHead1, pHead2->next);
}
return merge;
}说实话, 这个方案在力库上跑了下, 整体表现还可以. 不比非递归差多少.
那么非递归的思路也是一样, 新建一个节点, 每次对比两个链的值, 选择小的链上. 最后把剩余没跑完的, 一次性链接即可.
auto before = new ListNode(0);
auto cur = before;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 != nullptr ? l1 : l2;
return before->next;这里用到了一个哨兵节点, 等于保留了前一个节点的位置, 让问题简化很多.
反转链表
但是上面的问题, 这个点还不明显, 反转链表就很需要这样一个哨兵节点了.
ListNode *ReverseList(ListNode *head) {
if (head == nullptr) {
return nullptr;
}
ListNode *ret = nullptr;
auto move = head;
while (move) {
auto next = move->next;
move->next = ret;
ret = move;
move = next;
}
return ret;
}先保存当前点的next位置, 让next指到哨兵节点, 然后把当前位置赋值到哨兵节点, 等于是手动让其前进一步, 最后手动让当前节点走到其next. 其实就是双指针, 但是移动全靠手动赋值罢了.
最后
不是难题, 甚至没做过也能一下子ac, 不过从链表来看, 还是有价值的题目.
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录