原題鏈接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
目錄
1. 題目描述
2. 思路分析
3. 代碼實現
1. 題目描述
2. 思路分析
整體思路：創建兩個鏈表，分別存放小于x的結點和大于等于x的結點，分別進行尾插。
這道題目使用哨兵位會更簡單，原因如下（能避開很多為空的情況）：
（1）使用哨兵位就不需要考慮兩個鏈表尾插時為空的情況。
（2）兩個鏈表鏈接時也不需要考慮是否為空的情況。
（3）哪怕有一個鏈表為空，也有哨兵位的頭結點，正常鏈接即可。
我們用結構體指針lhead和ltail分別表示值小于x的那一條鏈表，用結構體指針ghead和gtail表示值大于等于x的那一條鏈表。
用malloc()函數分別申請兩個結點，也就是兩個鏈表的哨兵位，讓lhead和ltail一開始指向其中一個，ghead和gtail一開始指向另一個。
再創建一個結構體指針cur用來遍歷原鏈表，我們采用了while循環，當cur不為空時遍歷結點。
當結點的值小于x時，我們將這個結點尾插到第一個鏈表（ltail->next=cur）。再讓ltai往后走一步（ltai=ltail->next）。
當結點的值大于等于x時，我們將結點尾插到第二個鏈表（gtail->next=cur）。再讓gtail往后走一 一步（gtail=gtail->next）。
尾插一個結點后，讓cur往后走一步（cur=cur->next）。當cur為空時停止循環。
然后將兩個鏈表鏈接起來。（ltail->next=ghead->next）。
有一點需要非常注意！！！
將gtail->next=NULL
否則可能會出現環。
因為現在lhead指向的是哨兵位，所以我們要將lhead往后走一步（lhead=lhead->next）。
因為怕找不到lhead的下一個位置，所以我們引入一個結構體指針head保存lhead的下一個位置。（struct ListNode *head=lhead->next）。
然后為了防止內存泄漏，我們要用free()釋放掉兩個哨兵位（即free(lhed)和free(ghead)）。
最后返回head即可。
3. 代碼實現
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode *lhead,*ltail,*ghead,*gtail;lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *cur=pHead;while(cur){if(cur->val<x){ltail->next=cur;ltail=ltail->next;}else{gtail->next=cur;gtail=gtail->next;}cur=cur->next;}ltail->next=ghead->next;//不空，可能導致出現環gtail->next=NULL;struct ListNode *head=lhead->next;free(lhead);free(ghead);return head;}
};
)
