所屬專欄：玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)題型
博主首頁：初陽785
代碼托管：chuyang785
感謝大家的支持，您的點(diǎn)贊和關(guān)注是對(duì)我最大的支持?。。?br> 博主也會(huì)更加的努力，創(chuàng)作出更優(yōu)質(zhì)的博文??！
關(guān)注我，關(guān)注我，關(guān)注我，重要的事情說三遍?。。。。。。?！

1.題目來源

分割鏈表

2.題目描述

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)特定值 x ，請(qǐng)你對(duì)鏈表進(jìn)行分隔，使得所有 小于 x 的節(jié)點(diǎn)都出現(xiàn)在 大于或等于 x 的節(jié)點(diǎn)之前。
你不需要 保留 每個(gè)分區(qū)中各節(jié)點(diǎn)的初始相對(duì)位置。

3.解題思路

本題的意思就是說把下小于x的數(shù)據(jù)放在左邊，大于等于x的數(shù)據(jù)放在右邊，在改變順序的同時(shí)不改變?cè)瓉淼牡难颉?br> 我們的思路是創(chuàng)建兩個(gè)鏈表，一個(gè)鏈表LessHead放小于下的數(shù)據(jù)，另一個(gè)鏈表greaterHead放大于等于x的數(shù)據(jù)，最后把兩個(gè)兩邊合并成一個(gè)鏈表，然后返回新鏈表的首節(jié)點(diǎn)地址就行了。

為了方便鏈接，我們使用創(chuàng)建哨兵的方法來作為兩個(gè)鏈表的頭節(jié)點(diǎn)，所謂哨兵為就是它的val是無效數(shù)據(jù)，但是它的next指向下一個(gè)地址。
接著我們創(chuàng)建一個(gè)變量cur來遍歷我們的鏈表，然后根據(jù)他們的大小來給他們分配到不同的鏈表里去。

圖解：

當(dāng)x=3 的時(shí)候，cur開始遍歷，首先是第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)是1它比3小我們就把他鏈接到我們的LessHead鏈表中去，同時(shí)我們用LessNext來記錄鏈接過來的節(jié)點(diǎn)點(diǎn)的地址，在以后往后鏈接的時(shí)候只需要用LessHead表示就好，這樣的好處是鏈接完后我們返回鏈表的頭節(jié)點(diǎn)的地址的時(shí)候就直接返回LessHead就行了。

同樣的cur遍歷完第一個(gè)后只需要是cur=cur->next就可以訪問第二個(gè)節(jié)點(diǎn)了，因?yàn)槲覀冊(cè)阪溄拥谝粋€(gè)節(jié)點(diǎn)的時(shí)候并沒有破壞我們第一個(gè)節(jié)點(diǎn)指向我們第二個(gè)節(jié)點(diǎn)的通道，我們依然可以通過第一個(gè)節(jié)點(diǎn)找到第二個(gè)節(jié)點(diǎn)，同樣的我們用greaterNext來表示我們接下來的節(jié)點(diǎn)地址。

以此類推到我們的cur指向NULL的時(shí)候我們的循環(huán)就停止了。
接著就是將兩個(gè)鏈表合并就行。

我們只需要將lessTail->next=greaterHead->next;就行了。
但是這里有個(gè)特別重要的事情就是我們連接完后我們的greaterNext指向那里了？它真的就指向了NULL嗎？答案是否定的。
我們回到之前鏈接的時(shí)候：

我們看到這里我們的存放5數(shù)據(jù)的next是指向2的地址的。

所以他的圖像解析就變成了這個(gè)樣子，如果是這樣的話，就成環(huán)了，再返回地址的時(shí)候內(nèi)存就會(huì)出問題。
所以這里的解決方案就是把我們的greaterNext->next置空即：greaterNext->next=NULL。文章來源地址http://www.zghlxwxcb.cn/news/detail-444977.html

4.代碼展示

struct ListNode* partition(struct ListNode* head, int x)
{
    //創(chuàng)建哨兵位，方便鏈接
    struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
    //存放小于x的數(shù)據(jù)
    lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lessHead->next=NULL;
    
	//存放大于等于x的數(shù)據(jù)
    greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    greaterHead->next=NULL;
	
	//遍歷鏈表指針
    struct ListNode* cur=head;

    while(cur)
    {
        //尾插
        if(cur->val < x)
        {
            lessTail->next=cur;
            lessTail=cur;
        }
        else
        {
            greaterTail->next=cur;
            greaterTail=cur;
        }
        cur=cur->next;
    }
    //鏈接兩個(gè)鏈表
    lessTail->next=greaterHead->next;
    //消除環(huán)，我們的5最后還指向我們2，這個(gè)時(shí)候就形成了一個(gè)環(huán)、
    greaterTail->next=NULL;

    struct ListNode* newnode=lessHead->next;
    //最后釋放兩個(gè)創(chuàng)建的內(nèi)存空間
    free(lessHead);
    free(greaterHead);
    return newnode;
}

到了這里，關(guān)于【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（5）[分割鏈表]的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！