目錄

一、前言

二、題目描述?

三、解題方法

?? 頭插法 --- 創(chuàng)建新的鏈表

?? 迭代法 --- 三指針

?? 遞歸法

四、總結(jié)與提煉

五、共勉

---

一、前言

? ? ? ?反轉(zhuǎn)鏈表這道題，可以說是--鏈表專題--，最經(jīng)典的一道題，也是在面試中頻率最高的一道題目，通常在面試中，面試官可能會(huì)要求我們寫出多種解法來實(shí)現(xiàn)這道題目，所以大家需要對這道題目非常熟悉哦！！
? ? ? 本片博客就來詳細(xì)的講講解一下 反轉(zhuǎn)鏈表的多種實(shí)現(xiàn)方法，讓我們的面試變的更加順利！！！

二、題目描述?

?給你 單鏈表 的頭節(jié)點(diǎn)?head?，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

?三、解題方法

?? 頭插法 --- 創(chuàng)建新的鏈表

? ? ? ? 頭插這種方法，就是將結(jié)點(diǎn)一一地插入到新鏈表的頭前，所以我們需要先去建立出一個(gè)新的鏈表頭，也就是我下面的這個(gè)【rhead】，通過去遍歷原先的鏈表將這些結(jié)點(diǎn)一一轉(zhuǎn)移過去即可

• 定義三個(gè) 變量 cur 、newnode 、rhead?
• cur ：用于遍歷整個(gè)舊鏈表? ? ? ? ??newnode ：用于記錄cur的下一個(gè)節(jié)點(diǎn)，防止舊鏈表找不到
• rhead ：新鏈表的頭節(jié)點(diǎn)

// 重新創(chuàng)建一個(gè)鏈表，將之前的鏈表進(jìn)行頭插即可
struct ListNode* rphead = NULL;
// 進(jìn)行指針變換
struct ListNode* cur = head;

• ?開始頭插，cur 節(jié)點(diǎn)的 next 指向 rhead 節(jié)點(diǎn)，然后更新 rhead 、cur 、newnode 這三個(gè)節(jié)點(diǎn)

 // 用于保存下一個(gè)節(jié)點(diǎn)地址struct ListNode* newnode = cur->next;// 頭插cur->next = rphead;rphead = cur;cur = newnode;

• ?繼續(xù)同樣的操作

• 此時(shí)當(dāng)【cur == NULL】時(shí)，便結(jié)束一個(gè)遍歷，然后新鏈表的頭就是【rhead】，返回即可

?完整代碼：

struct ListNode* reverseList(struct ListNode* head)
{// 重新創(chuàng)建一個(gè)鏈表，將之前的鏈表進(jìn)行頭插即可struct ListNode* rphead = nullptr;// 進(jìn)行指針變換struct ListNode* cur = head;while(cur!=NULL){// 用于保存下一個(gè)節(jié)點(diǎn)地址struct ListNode* newnode = cur->next;// 頭插cur->next = rphead;rphead = cur;cur = newnode;}return rphead;
}

?? 迭代法 --- 三指針

? ? ? ? ?三指針的迭代方法，這種方法不需要在去創(chuàng)建一個(gè)新的頭結(jié)點(diǎn)指針，只需要在原先的鏈表上進(jìn)行一個(gè)操作即可，也就是定義三個(gè)指針。

• cur：指向當(dāng)前鏈表的頭
• nextnode：指向cur的next，一樣是用于保存。
• prev：這個(gè)的話其實(shí)是用來算作鏈表最后一個(gè)結(jié)點(diǎn)指向空的。

ListNode* prev = nullptr;
ListNode* cur = head;
ListNode* nextNode = cur->next;

• 然后將【cur->next = prev】，讓原本的頭【cur】作為反轉(zhuǎn)后新鏈表的尾巴

• 接著就是進(jìn)行的一個(gè)迭代操作，首先將【cur】當(dāng)前的值給到【prev】，然后將【nextnode】當(dāng)前的值給到【cur】，然后讓【nextnode】繼續(xù)向下，這個(gè)時(shí)候其實(shí)就進(jìn)行了一個(gè)迭代的操作

• cur->next = prev;
  prev = cur;
  cur = nextnode;

• 

• 然后繼續(xù)做翻轉(zhuǎn)，讓【cur->next】指向?prev, 并更新三個(gè)指針

• 可以看到，當(dāng)這個(gè)【cur == NULL】時(shí)，整個(gè)鏈表便完成了一個(gè)翻轉(zhuǎn)，此時(shí)便結(jié)束循環(huán)迭代的邏輯

• 然后可以看到，此時(shí)新鏈表的頭并不是【cur】，而是【prev】，所以最后應(yīng)該返回【prev】

?完整代碼：

class Solution {
public:ListNode* reverseList(ListNode* head) {// 1. 迭代法// 定義三個(gè)指針ListNode* prev = nullptr;      // cur 的前一個(gè)節(jié)點(diǎn)ListNode* cur = head;// 開始迭代while(cur!=nullptr){ListNode* nextnode = cur->next;  // cur的下一個(gè)指針cur->next = prev;prev = cur;cur = nextnode;}return prev;}
};

?? 遞歸法

我們可以通過迭代的方法來得到遞歸方法?

• 函數(shù)聲明中 prev 指針指向的為 NULL，cur 指針指向的為 head，正如遞歸中聲明并初始化的prev 和 cur?指針
• 遞歸結(jié)束條件為 cur 為 NULL, 返回 prev
• 同樣?newnode?保存 cur 的下一個(gè)節(jié)點(diǎn)，以防止反轉(zhuǎn)時(shí)丟失鏈表信息。
• 然后進(jìn)行反轉(zhuǎn) cur->next = prev;
• prev為當(dāng)前已反轉(zhuǎn)部分的頭節(jié)點(diǎn)，cur為當(dāng)前待反轉(zhuǎn)的節(jié)點(diǎn)。
• 然后調(diào)用遞歸，將cur作為新的 prev 傳入下一層，將 newnode 作為新的 cur 傳入下一層。
• 實(shí)現(xiàn)了鏈表的遞歸反轉(zhuǎn)

class Solution {
public:ListNode* reverse(ListNode* prev, ListNode* cur){// 最終結(jié)束條件if(cur==nullptr){return prev;}ListNode* newnode =cur->next;cur->next = prev;// 將 cur 作為 prev 傳入下一層// 將 newnode 作為 cur 傳入下一層，改變其指針指向當(dāng)前 curreturn reverse(cur,newnode);}ListNode* reverseList(ListNode* head) {// 3. 遞歸法return reverse(nullptr,head);}
};

?四、總結(jié)與提煉

? ? ? ? ?最后我們來總結(jié)一下本文所介紹的內(nèi)容，本文講解來一道力扣中有關(guān)鏈表翻轉(zhuǎn)的題目，這道題目是校招筆試面試中有關(guān)鏈表章節(jié)非常高頻的一道題目，大家下去一定要自己再畫畫圖，分析一下，把這段代碼邏輯自己實(shí)現(xiàn)一遍，才能更好地掌握

?五、共勉

? ? ? ?以下就是我對 反轉(zhuǎn)鏈表?的理解，如果有不懂和發(fā)現(xiàn)問題的小伙伴，請?jiān)谠u論區(qū)說出來哦，同時(shí)我還會(huì)繼續(xù)更新對 鏈表專題?的理解，請持續(xù)關(guān)注我哦！！！????