片頭

嗨！小伙伴們，大家好！今天我們一起來看看這道題----分隔鏈表

emmmm，這道題，看描述應該不算太難，我們一起來畫一畫圖唄！

題目讀懂了，那么如何破解這道題呢？

思路：定義2個鏈表，大鏈表和小鏈表，遍歷原鏈表的節點將其放到對應的新鏈表中，最后將大鏈表和小鏈表首尾相連。

第一次：

第二次：

第三次：

第四次：

第五次：

?第六次：

OK,現在pcur在原鏈表中，已經走到NULL的位置，循環結束，部分代碼如下：

         typedef struct ListNode ListNode;//如果鏈表為空，返回空if(head == NULL){return head;}//pcur遍歷原鏈表ListNode* pcur = head;//創建小鏈表，創建小鏈表的哨兵節點ListNode* lessHead = NULL;ListNode* lessTail = NULL;lessHead = lessTail =(ListNode*) malloc(sizeof(ListNode));//創建大鏈表，創建大鏈表的哨兵節點ListNode* greateHead = NULL;ListNode* greateTail = NULL;greateHead = greateTail =(ListNode*) malloc(sizeof(ListNode));//當pcur遍歷到空時，退出循環while(pcur!=NULL){if(pcur->val < x){//尾插到小鏈表中lessTail->next = pcur;lessTail = pcur;}else{//尾插到大鏈表中greateTail->next = pcur;greateTail = pcur;}//pcur指向下一個節點pcur = pcur->next;}

?接下來，我們需要讓greateTail的next指針指向NULL，如果不置為NULL的話，就會形成一個環，

下一步，怎么讓小鏈表和大鏈表連接起來呢？很簡單，讓 lessTail->next = greateHead->next 就可以啦！

最后一步，就是用一個節點來保存第一個節點，把2個哨兵節點釋放,返回第一個有效節點就可以啦！

ListNode* ret = lessHead->next;
free(lessHead);
free(greateHead);
return ret;

OK，這道題被我們解決了，完整代碼如下：

 typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {//如果鏈表為空，返回空if(head == NULL){return head;}//pcur遍歷原鏈表ListNode* pcur = head;//創建小鏈表，創建小鏈表的哨兵節點ListNode* lessHead = NULL;ListNode* lessTail = NULL;lessHead = lessTail =(ListNode*) malloc(sizeof(ListNode));//創建大鏈表，創建大鏈表的哨兵節點ListNode* greateHead = NULL;ListNode* greateTail = NULL;greateHead = greateTail =(ListNode*) malloc(sizeof(ListNode));//當pcur遍歷到空時，退出循環while(pcur!=NULL){if(pcur->val < x){//尾插到小鏈表中lessTail->next = pcur;lessTail = pcur;}else{//尾插到大鏈表中greateTail->next = pcur;greateTail = pcur;}//pcur指向下一個節點pcur = pcur->next;}//大鏈表最后一個結點的next指針指向NULLgreateTail->next = NULL;//小鏈表最后一個節點指向大鏈表的第一個有效節點lessTail->next = greateHead->next;//用ret來保存小鏈表的第一個有效節點ListNode* ret = lessHead->next;//將哨兵節點釋放free(lessHead);free(greateHead);//將ret返回return ret;
}

片尾

今天我們學習了一道OJ題---分隔鏈表，希望看完這篇文章能對友友們有所幫助！！！

?求點贊收藏和關注！！！

謝謝大家！！！