题目来源：
题目描述：
代码实现：
1.带哨兵位的头结点
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* lesshead = NULL, * lesstail = NULL, * greaterhead = NULL, * greatertail = NULL, * cur = pHead; lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode)); while (cur) { //尾插 if (cur->val < x) { lesstail->next = cur; lesstail = lesstail->next; } else { greatertail->next = cur; greatertail = greatertail->next; } //迭代 cur = cur->next; } //连接 lesstail->next = greaterhead->next; //置空大头尾结点的next greatertail->next = NULL; //将新的头结点指针赋给原头结点指针 pHead = lesshead->next; //释放大小头结点并置空 free(lesshead); lesshead = NULL; free(greaterhead); greaterhead = NULL; return pHead; } };
2.不带哨兵位的头结点
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* lesshead = NULL, * lesstail = NULL, * greaterhead = NULL, * greatertail = NULL; while (pHead) { //尾插 if (pHead->val < x) { if(NULL == lesstail) { lesshead = lesstail = pHead; } else { lesstail->next = pHead; lesstail = lesstail->next; } } else { if(NULL == greatertail) { greaterhead = greatertail = pHead; } else { greatertail->next = pHead; greatertail = greatertail->next; } } //迭代 pHead = pHead->next; } //小头为空 if(lesshead != NULL && greaterhead == NULL) { lesstail = NULL; return lesshead; } //大头为空 if(lesshead == NULL && greaterhead != NULL) { greatertail = NULL; return greaterhead; } //连接 lesstail->next = greaterhead; //置空大头尾结点的next greatertail->next = NULL; return lesshead; } };
思路分析：
1.带哨兵位的头结点
为实现本题，我们先将原链表头结点赋给cur，再开辟两个结构体，并将其分别赋给结构体指针变量，lesshead = lesstail，greaterhead = greatertail。小于 x 尾插在 lesstail->next 上，大于 x 尾插在 greatertail->next 上。
实现过程：
1.创建两个带哨兵位的新链表，分别存放小于 x 的所有结点和大于 x 的所有结点。我们定义小于 x 的头尾结点为lesshead，lesstail；定义大于 x 的头尾结点为 greaterhead，greatertail。
2.遍历链表，val < x 那么就尾插在 lesstail->next，val > x 那么就尾插在 greatertail->next。然后更新原链表的头结点和插入后的尾指针，分别都往后走一步。
3.循环步骤2，遍历完整个原链表，这时也就将大小分开了，再将 lesstail->next = greaterhead->next 并将greatertail->next = NULL，再将新的头结点赋值给原链表头，pHead = lesshead->next（因为最后要释放掉lesshead与greaterhead，并置空，所以要将小头结点赋值给pHead）。
4.释放 lesshead，greaterhead，并返回 pHead。
易错点：
可能会出现环形链表：
为了避免这种情况的发生，我们最后将 greatertail->next = NULL 处理，这样就避免了这种情况。
2.不带哨兵位的头结点
主要的思路是一致的，只是这次我们不开辟结构体，直接定义结构体指针lesshead、lesstail，greaterhead、greatertail，并将其置空。
实现过程：
与带哨兵位的头结点实现过程类似，不同点：
1.连接那块，lesstail->next = greaterhead，因为这次没有哨兵位，不用连接next。
2.返回值lesshead不是动态开辟的，不用释放，因此就不用再赋回去，直接返回 lesshead。
易错点：
1> 可能会出现环形链表：
为了避免这种情况的发生，我们最后将 greatertail->next = NULL 处理，这样就避免了这种情况。
2> 将大小分开后 lesshead或者greaterhead 可能为空，需要判断：
//小头为空 if(lesshead != NULL && greaterhead == NULL) { lesstail = NULL; return lesshead; } //大头为空 if(lesshead == NULL && greaterhead != NULL) { greatertail = NULL; return greaterhead; }
如果大牛的您看到有什么问题留言给我，我一定会认真看的，谢谢您。如果您看了觉得有收获，关注 + 点赞支持一下呗。
*** 本篇结束 ***
