【线性表】—带头哨兵卫单链表的应用
目录
前言
我们之前学过了无头单向非循环链表的实现，但是我们发现，该链表在尾插的时候有一点不好，就是第一次尾插时，会改变头节点，所以我们在上篇文章实现时传的是二级指针。
而本次所讲哨兵卫单链表在尾插时则不用改变头节点。所谓哨兵卫，其实就是带了一个头节点，该节点不作为用来存储数据。如下：
接下来我们通过具体题目来感受该结构带来的好处。
实战练习
链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：假如这道题不是一个链表题，而是一个数组题，我相信大家很多人都会想到这么一个办法，开辟两个数组，然后对原数组进行遍历，<x的放在arr1中，剩下的放在arr2中，然后再将arr2合并到arr1中。 对于链表题我们也可以这么来搞，用两个链表分别链接<x以及其余的，最后再合并两个链表。不过这里我们用哨兵卫单链表实现的话，就不需要考虑到链表是否为空的情况。如下：
代码实现：
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
//哨兵卫单链表，两个单链表分别存放<x和>x，最后合并
ListNode* newnode1 = (ListNode*)malloc(sizeof(ListNode));
ListNode* newnode2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail1 = newnode1;
ListNode* tail2 = newnode2;
while (pHead) {
//<x的放在newnode1链表
if (pHead->val < x) {
tail1->next = pHead;
tail1 = tail1->next;
}
//>=x的放在newnode2链表
else {
tail2->next = pHead;
tail2 = tail2->next;
}
pHead = pHead->next;
}
//链接两个链表
tail1->next=newnode2->next;
tail2->next=NULL;//一定记得置空！否则又可能出现死循环
struct ListNode*phead=newnode1->next;//保存下一个节点
//释放
free(newnode1);
free(newnode2);
return phead;
}
};这里我们就不需要考虑链表是否为空的情况，会省很多事，因此对于一些单链表的题目，只要涉及到尾插问题，建议使用带头哨兵卫单链表。并且再次强调，一定要多画图！
合并两个有序链表
这道题，把它想象成一个普通的题，我们应该都会做，即双指针遍历，然后取小尾插。这里需要注意的是，当一方遍历完，另一方没完时，直接将没完的那一方插入即可。这里涉及到尾插，为了不用考虑空表情况下的尾插，我们依然采用哨兵卫单链表。如下：
代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//开辟一个新节点
struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
newnode->next=NULL;
struct ListNode*tail=newnode;
while(list1 && list2)
{
//取小尾插
if(list1->val < list2->val)
{
tail->next=list1;
tail=tail->next;
list1=list1->next;
}
else
{
tail->next=list2;
tail=tail->next;
list2=list2->next;
}
}
//list2为空
if(list1)
{
tail->next=list1;
}
//list1为空
if(list2)
{
tail->next=list2;
}
//保存头节点的下一个节点
struct ListNode*newhead=newnode->next;
//释放
free(newnode);
return newhead;
}总结
** 对于需要进行尾插的链表，我们采用带头哨兵卫单链表用来实现尾插，会省事很多，不用考虑空表的存在，不过要注意的是，因为这个哨兵卫节点是我们malloc出来的，所以最后一定记得释放，并且哨兵卫节点的下一个节点才是用来存储有效数据的，另！一定要多画图！ **
腾讯云开发者
