目录
前言
实战练习
链表分割
合并两个有序链表
总结
前言
我们之前学过了无头单向非循环链表的实现，但是我们发现，该链表在尾插的时候有一点不好，就是第一次尾插时，会改变头节点，所以我们在上篇文章实现时传的是二级指针。
而本次所讲哨兵卫单链表在尾插时则不用改变头节点。所谓哨兵卫，其实就是带了一个头节点，该节点不作为用来存储数据。如下：
接下来我们通过具体题目来感受该结构带来的好处。
实战练习
链表分割
现有一链表的头指针 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出来的，所以最后一定记得释放，并且哨兵卫节点的下一个节点才是用来存储有效数据的，另！一定要多画图！ **
