一、题目
函数原型：
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 here ListNode *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 here ListNode *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; } } };
