前言

• 本章的OJ練習(xí)相對(duì)前面的難度加大了，但是換湯不換藥，還是圍繞單鏈表的性質(zhì)來出題的。我相信，能夠過了前面的OJ練習(xí)，本章的OJ也是輕輕松松。

• 對(duì)于OJ練習(xí)(3)：-> 傳送門 <- ，著重需要理解的是相交鏈表那道題的雙指針?biāo)悸?#xff0c;明白為什么可以這樣，這樣為什么可行。后面遇到類似的題目我還會(huì)做么？

• 我們每做一道題目，都要深挖他的題目結(jié)構(gòu)，明白為什么可以這樣做。我相信如果你這樣去做了，并且不斷地練習(xí)，到后面，每遇到一個(gè)題目，你都會(huì)有所印象，并能夠很快的指出解這道題的思路。

分割鏈表

• 題目鏈接：-> 傳送門 <- 。

• 題目描述：現(xiàn)有一鏈表的頭指針 ListNode* pHead，給一定值x，編寫一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變?cè)瓉淼臄?shù)據(jù)順序，返回重新排列后的鏈表的頭指針。

• 這里的不能改變?cè)瓉淼臄?shù)據(jù)順序，也就是比x小的節(jié)點(diǎn)放在其余節(jié)點(diǎn)之前時(shí)，這些節(jié)點(diǎn)的順序應(yīng)該與沒有放之前是一樣的。

• 例如: 2 4 8 5 9 3 5 ，給定 x = 8，通過本題目的描述最終的答案應(yīng)該為：2 4 5 3 5 8 9 。

圖解描述：（給定x = 3）

解題思路：

• 根據(jù)題目的意思以及不能改變?cè)瓉淼臄?shù)據(jù)順序這一特性，我們可以以一種反歸并的思想來想這道題。

• 我們遍歷原鏈表并創(chuàng)建兩個(gè)新鏈表（這里的新鏈表表示的是在原鏈表基礎(chǔ)上通過某一條件新連接的一串節(jié)點(diǎn)），第一個(gè)鏈表用來尾插小于x的節(jié)點(diǎn)，第二個(gè)鏈表用來尾插大于等于x的節(jié)點(diǎn)，最后再將第一個(gè)鏈表的尾與第二個(gè)鏈表的頭相連接，再返回連接后的整個(gè)鏈表的頭，便ok啦。整個(gè)解題思路大致是這樣，后面，來談?wù)勂渲械募?xì)節(jié)。

• 對(duì)于創(chuàng)建的兩個(gè)新鏈表，都需要哨兵位的頭節(jié)點(diǎn)來維護(hù)，什么是哨兵位的頭節(jié)點(diǎn)呢？我們可以把哨兵位的頭節(jié)點(diǎn)當(dāng)作真實(shí)頭節(jié)點(diǎn)的前驅(qū)，它是一個(gè)不在答案范圍內(nèi)的節(jié)點(diǎn)，但它卻可以有效的控制真實(shí)的鏈表。其里面的值可以是隨機(jī)的，它的next初始指向NULL，直到有節(jié)點(diǎn)尾插，它的next就指向這個(gè)節(jié)點(diǎn),而這個(gè)節(jié)點(diǎn)就是新連接的鏈表的真實(shí)的頭。當(dāng)最后連接完成時(shí)，我們想要返回這個(gè)鏈表，應(yīng)該返回哨兵位的next，因?yàn)樯诒坏?code>next才是有效的真實(shí)的頭節(jié)點(diǎn)。

• 如果說不用哨兵位的頭節(jié)點(diǎn)來維護(hù)，也是可以的。不過這樣會(huì)有很多不必要的處理。比如給的原鏈表是NULL,或者兩個(gè)新鏈表連接完后其中有一個(gè)為空，這些都有可能造成解題出問題，因此需要額外的處理。所以，為了減少這些麻煩，用哨兵位的頭節(jié)點(diǎn)來維護(hù)這兩個(gè)新鏈表，上述的這些情況都能夠有效避之（上手寫代碼就有深刻的體會(huì)）。

• 有了上面的鋪墊我們只需要按照題目要求依次在原鏈表取節(jié)點(diǎn)，然后在對(duì)應(yīng)哨兵位節(jié)點(diǎn)指向的鏈表中尾插，最后將這兩個(gè)鏈表連接即可。

下面是代碼實(shí)現(xiàn)：

這里沒學(xué)過c++也不用擔(dān)心，代碼純都是C語言寫的。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// 創(chuàng)建兩個(gè)哨兵位的頭節(jié)點(diǎn)// nhead作為連接比x小的節(jié)點(diǎn)// rhead作為連接大于等于x的節(jié)點(diǎn)struct ListNode* nhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* rhead = (struct ListNode*)malloc(sizeof(struct ListNode));// 操控連接的指針nhead->next = NULL, rhead->next = NULL;struct ListNode* cur = pHead, * cur1 = nhead, * cur2 = rhead;// 遍歷原鏈表while (cur){// 如果小于x就尾插到nheadif (cur->val < x) {cur1->next = cur;cur1 = cur1->next;}else   // 如果 >= x 就尾插到rhead{cur2->next = cur;cur2 = cur2->next;}cur = cur->next;}// 兩個(gè)帶哨兵位頭節(jié)點(diǎn)的鏈表的連接// 第一個(gè)的尾連接第二個(gè)的頭cur1->next = rhead->next;// 將第二個(gè)的尾置為NULLcur2->next = NULL;// 保存連接好的整個(gè)鏈表的頭節(jié)點(diǎn)（哨兵位頭節(jié)點(diǎn)的下一個(gè)）struct ListNode* newhead = nhead->next;// 分別釋放創(chuàng)建的兩個(gè)哨兵位頭節(jié)點(diǎn)free(nhead);free(rhead);// 返回新鏈表的頭return newhead;}
};

---

回文鏈表

• 題目鏈接：-> 傳送門 <- 。

• 題目描述：給你一個(gè)單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。

• 回文結(jié)構(gòu)，相信大家已不陌生，類似于12321，123321，6789876這樣的數(shù)字，都可稱之為回文數(shù)。而回文鏈表也是一樣，它每個(gè)節(jié)點(diǎn)的值組成的數(shù)就是一個(gè)回文數(shù)，例如下面這些鏈表：

• 那么我們?cè)撊绾闻袛嘁粋€(gè)鏈表是否為回文鏈表呢？

解題思路一：

• 我們可以在不破壞原鏈表的情況下另外創(chuàng)建一個(gè)鏈表，通過遍歷原鏈表依次將原鏈表上的節(jié)點(diǎn)復(fù)制尾插到新鏈表。

• 然后兩個(gè)鏈表從頭開始比較，如果有一個(gè)節(jié)點(diǎn)的值不相等就返回false。兩個(gè)鏈表都遍歷結(jié)束并且最后遍歷的指針都同時(shí)指向NULL，此時(shí)返回true。

下面是代碼實(shí)現(xiàn)：

bool isPalindrome(struct ListNode* head){struct ListNode* rhead = NULL;struct ListNode* cur = head;// 尾插到新鏈表while (cur){if (rhead == NULL){rhead = (struct ListNode*)malloc(sizeof(struct ListNode));rhead->val = cur->val;rhead->next = NULL;}else {struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));newnode->val = cur->val;newnode->next = rhead;rhead = newnode;}cur = cur->next;}struct ListNode* cur1 = head, * cur2 = rhead;while (cur1 && cur2){// 有不同直接返回falseif (cur1->val != cur2->val) return false;cur1 = cur1->next;cur2 = cur2->next;}// 如果結(jié)束且同時(shí)指向NULL，說明回文if (cur1 == NULL && cur2 == NULL) return true;else return false;
}

該思路可以說是暴力解法，效率相對(duì)較低，并且開了額外的空間，如果限制不能開額外的空間呢？

解題思路二：

• 上一個(gè)思路創(chuàng)建了額外的空間，而本思路將不創(chuàng)建新的空間。

• 首先，找到鏈表的中間節(jié)點(diǎn)，然后從這個(gè)中間節(jié)點(diǎn)開始，將后面的節(jié)點(diǎn)逆轉(zhuǎn)，最后從鏈表的頭節(jié)點(diǎn)和逆轉(zhuǎn)后返回的節(jié)點(diǎn)分別開始遍歷判斷。

• 如下圖解析：

• 可以看到，整個(gè)判斷過程是一個(gè)循環(huán)，如果rhead指向空就結(jié)束循環(huán)，說明是回文鏈表；如果在循環(huán)期間，發(fā)現(xiàn)有不一樣的值的節(jié)點(diǎn)，就直接返回false。

• 對(duì)于 -> 找中間節(jié)點(diǎn) <- 和 -> 反轉(zhuǎn)鏈表 <- ，在前面已經(jīng)講解過了，在這里，我們直接 ctrl + c , ctrl + v 就好。

下面是代碼實(shí)現(xiàn)：

// 尋找中間節(jié)點(diǎn)函數(shù)
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head, * slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}// 反轉(zhuǎn)鏈表函數(shù)
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* prev =  NULL;while (cur){struct ListNode* tmp = cur->next;cur->next = prev;prev = cur;cur = tmp;}return prev;
}bool isPalindrome(struct ListNode* head){// 找中間節(jié)點(diǎn)struct ListNode* mid = middleNode(head);// 從中間節(jié)點(diǎn)開始反轉(zhuǎn)鏈表struct ListNode* rlist = reverseList(mid);// 判斷while (rlist){if (head->val != rlist->val) return false;rlist = rlist->next;head = head->next;}       return true;
}

---

寫在最后

對(duì)于單鏈表的題目練習(xí)，最重要的是思路，我們?cè)跀?shù)據(jù)結(jié)構(gòu)階段要養(yǎng)成畫圖的習(xí)慣，因?yàn)樗軒椭覀兏玫睦斫?。后續(xù)還會(huì)有單鏈表相關(guān)的題目練習(xí)。

感謝閱讀本小白的博客，錯(cuò)誤的地方請(qǐng)嚴(yán)厲指出噢！