牛客网：链表分割

一、题目

函数原型：

ListNode* partition(ListNode* pHead, int x)

二、思路

根据题意，可以设置两个新的链表，将原链表中所有小于x的结点链接到链表1中，大于x的结点链接到链表2中，最后再将两个链表合并即可。

此题有两种写法，一种是带哨兵位的链表，另一种是不带哨兵位的链表。

 实际操作过程中，发现对于两个链表的合并，带哨兵位链表比不带哨兵位链表的代码更加简洁。

（带哨兵位的结点进行尾插时不需要考虑头结点是否为空，且链表合并时可以直接合并，无需考虑某一链表是否为空的情况）

三、代码

代码实现1（带哨兵位）

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode *Bnewhead=(ListNode*)malloc(sizeof(ListNode));//小链表的哨兵位ListNode *Btail=Bnewhead;//大链表尾指针ListNode *Snewhead=(ListNode*)malloc(sizeof(ListNode));//大链表的哨兵位ListNode *Stail=Snewhead;//小链表尾指针ListNode *cur=pHead;//遍历指针while(cur){if(cur->val<x)//结点值小于x，尾插到小链表{Stail->next=cur;Stail=cur;}else//结点大于x，尾插到大链表{Btail->next=cur;Btail=cur;}cur=cur->next;}Stail->next=NULL;//小链表尾结点指针域指向空Btail->next=NULL;//大链表尾结点指针域指向空Stail->next=Bnewhead->next;//将大小链表合并return Snewhead->next;//返回新链表的头结点（非哨兵位）}
};

代码实现2（不带哨兵位）

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode *cur=pHead;ListNode *Bnewhead=NULL;//大链表头结点ListNode *Btail=NULL;//大链表尾指针ListNode *Snewhead=NULL;//小链表头结点ListNode *Stail=NULL;//小链表尾指针while(cur)//遍历原链表{if(cur->val<x)//结点值小于x，尾插到小链表{if(Stail==NULL)//先判断小链表是否为空，为空则将插入结点作为头结点{Snewhead=Stail=cur;}else//小链表不为空，进行尾插{Stail->next=cur;Stail=cur;}}else{if(Btail==NULL)//先判断大链表是否为空，为空则将插入结点作为头结点{Bnewhead=Btail=cur;}else//大链表不为空，进行尾插{Btail->next=cur;Btail=cur;}}cur=cur->next;}if(Btail)//将大链表尾结点指针域指向空Btail->next=NULL;if(Stail)//将小链表尾结点指针域指向空Stail->next=NULL;//开始合并大小链表if(Stail==NULL)//如果小链表为空，则直接返回大链表{return Bnewhead;}else if(Btail==NULL)//如果大链表为空，则直接返回小链表{return Snewhead;}else if(Stail==NULL&&Btail==NULL)//如果大小链表都为空，则直接返回空{return NULL;}else//大小链表都不为空，将两个链表合并{Stail->next=Bnewhead;return Snewhead;} }
};