本文主要是介绍带哨兵位的单链表之 链表分割，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
认识
链表分为两种：带头结点的和不带头结点的
之前我们学习了不带哨兵位的单链表，并实现了相关代码
现在我们认识一下带哨兵位头结点的单链表：
plist指向带哨兵位的头结点
这个结点不存储有效数据
如果为空链表：
- 不带头：plist指向NULL
- 带头：plist指向head，一定不会指向NULL
优势
带哨兵位的单链表也有他自己的优势，我们用一道题来证明一下：
链表分割_牛客题霸_牛客网 (nowcoder.com)
题目描述：
题目分析
假设有下面这个链表，给定数字5
那么排序后就是这样，不改变原来是数据顺序
可以分割成两个链表，plist1和plist2，小于x的结点尾插到plist1，否则尾插到plist2
当链表的数据全部尾插结束后，将plist2头结点尾插到plist1，这个时候带哨兵位的头结点就非常有优势了
我们可以定义两个头结点head和head2，分别作为两个链表的哨兵位，再定义两个尾结点tail1和tail2方便两个链表的尾插，定义cur遍历链表，和x值做比较
代码示例
我们思路清晰了就可以写代码了：
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* head1,* head2,* tail1,* tail2;head1=(struct ListNode*)malloc(sizeof(struct ListNode));head2=(struct ListNode*)malloc(sizeof(struct ListNode));tail1=head1;tail2=head2;struct ListNode* cur=pHead;while(cur){if(cur->val<x){tail1->next=cur;tail1=tail1->next;}else{tail2->next=cur;tail2=tail2->next;}cur=cur->next;}tail1->next=head2->next;tail2->next=NULL;pHead=head1->next;free(head1);free(head2);return pHead;}
};由于该题只能用c++，但是我们可以完全按照C语言的语法规则写内部，最后就可以通过了;
这篇关于带哨兵位的单链表之 链表分割的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
