給定一個頭結點和一個值x，是鏈表中所有小于x的值都在x前面

?typedef struct ListNode ListNode;

struct ListNode* partition(struct ListNode* head, int x) {

? ? //思路一：在原鏈表上進行修改

? ? //思路二：創建新鏈表，使用哨兵位，比x大的尾插，比x小的頭插

? ? //思路三：創建兩個鏈表，一個是大鏈表，一個是小鏈表，都整一個哨兵位

? ? if(head == NULL)

? ? {

? ? ? ? return head;

? ? }

? ? ListNode* lesshead = (ListNode*)malloc(sizeof(ListNode));

? ? ListNode* greaterhead = (ListNode*)malloc(sizeof(ListNode));

? ? ListNode* lesstail = lesshead;

? ? ListNode* greatertail = greaterhead;

? ? ListNode* pcur = head;

? ? while(pcur)

? ? {

? ? ? ? if(pcur->val < x)

? ? ? ? {

? ? ? ? ? ? lesstail->next = pcur;

? ? ? ? ? ? lesstail = lesstail->next;

? ? ? ? }

? ? ? ? else

? ? ? ? {

? ? ? ? ? ? greatertail->next = pcur;

? ? ? ? ? ? greatertail = greatertail->next;

? ? ? ? }

? ? ? ? pcur = pcur->next;

? ? }

? ? //小鏈表的尾節點與大鏈表的第一個有效節點結合

? ? greatertail->next = NULL;//防止死循環，并將next指針初始化

? ? lesstail->next = greaterhead->next;

? ? ListNode* ret = lesshead->next;

? ?

? ? free(lesshead);

? ? free(greaterhead);

? ? lesshead = greaterhead = NULL;

? ? return ret;

}

//超出時間限制只有一種情況：就是代碼出現了死循環

//創建新鏈表時，若進行尾插，則要考慮