單向鏈表反轉，就地逆置與遞歸反轉（無表頭結點）
- 2019 年 10 月 3 日
- 筆記
最近在看鏈表，今天刷到一道鏈表的反轉題，鏈表反轉可以說是基礎操作，但是可提供的方案也有很多，簡單通過了該題後又學習了一下遞歸反轉，現在把三種方法都公開出來做一個總結。
1.就地逆置
2.單參數的遞歸逆置
3.雙參數的遞歸逆置
一、就地逆置
方法：頭插。
由於這裡是不帶表頭結點的單向鏈表，所以頭插會稍微複雜一點，不想往下看的小夥伴也可以直接選擇定義一個臨時表頭結點從頭結點開始遍歷鏈表將每一個鏈表頭插，最後將頭結點指向表頭結點的next指針域，最後free掉那個表頭結點即可。
雖然不帶表頭結點頭插會稍微複雜一些，但是只要加一條語句就可以解決問題。
在不帶表頭結點的單向鏈表中進行頭插，唯一要特殊處理的地方就是頭結點。而中間結點和尾結點的頭插可以簡化為下面的程式碼段
pre->next = head;
head = pre;
在找到普遍規律後，接下來就要考慮特殊情況是否能適應普遍規律。在這裡如果pre指向鏈表頭結點，pre->next = head;則產生一個環，導致的結果就是在鏈表遍歷結束後，尾部會產生一個長度為1的環。
而我們想要的尾部應該是指向NULL的，所以很顯然，if pre == head, pre->next = NULL; 為了使程式碼更加美觀具有統一性，所以我們增設一個指針 q，初始值為NULL即可。
程式碼如下
ElemSN *ReverseList(ElemSN *head) { ElemSN *q = NULL; ElemSN *p = h; // 指針p 遍歷鏈表 while(p){ ElemSN *pre = p; // pre指向當前要處理的結點 p = p->next; // p 走到下一個結點候命 m->next = q; q = head = m; } return head; }
————————以下為9.6號補充—————–
上面這段就地逆置程式碼本質上為創建鏈表，下面給出同等效果的另一種形式。（這種形式將節省一個指針p的空間，並用head來代替p遍歷鏈表，用h1指針指向所創建新鏈的頭結點，這種形式更加突出的體現了以建鏈來逆置鏈表的思想）
ElemSN *ReverseList(ElemSN *head) { ElemSN *h1 = NULL; ElemSN *q; while(head){ q = head; head = head->next; q->next = h1; h1 = q; } return h1; }
至於選用哪種方法依個人愛好即可，這裡只是貼出來發散一下思維。
—————————end———————————
二、單參數遞歸逆置
如果單向鏈表可以從後向前遍歷，那我想要逆置鏈表不就變得容易的多，只需要從尾結點開始不斷的讓尾結點指向前一個結點即可。
但事實上單向鏈表只能單向遍歷，如果想要直接逆向遍歷是幾乎不可能的，但是遞歸間接的幫我們實現了這個功能。
先擺一下函數聲明
ElemSN *ReverseList(ElemSN *head);
遞歸無非就是自己調用自己，理解遞歸其實很容易，在遞歸里，ReverseList函數每調用自己一次，都相當於將該函數全部程式碼粘貼到函數調用處一次，直到某次調用自己時觸發了return 返回，然後不斷的返回返回，直到返回到第一次調用，最終返回一個結果值。
因此看一個簡單的遞歸函數
ElemSN *ReverseList(ElemSN *head) { if(head->next == NULL || head == NULL){ return head; }
ElemSN *nextNode = head->next; ElemSN *reverseNode = ReverseList(nextNode); return reverseNode; }
該函數通過不斷調用自己實現對鏈表的遍歷，並且該函數將head->next == NULL作為函數第一次的返回點，也就是當形參head到達尾結點時開始返回，之後每次返回都會將該結點傳至上一層調用，直至到達最頂層調用時返回尾結點。
可見遞歸，從最頂層開始逐級調用自己的過程是從頭到尾遍歷鏈表的過程，而從最底層調用開始逐級返回則是一個由尾到頭遍歷鏈表的過程。而我們要做的逆置操作就從函數逐級返回開始，因此我們就可以利用這一特性寫出下面的遞歸逆置程式碼
ElemSN *ReverseList(ElemSN *head) { if(head->next == NULL || head == NULL){ return head; // 設定最底層調用返回點，到達尾結點後開始返回 } ElemSN *nextNode = head->next; head->next = NULL; //很重要的一條語句哦，如果省略依舊會在新生成的鏈表尾部產生一個長度為1的環哦，可以注釋掉本條程式碼運行再查看一下輸出結果 ElemSN *reverseNode = ReverseList(nextNode); // 遞歸遍歷鏈表 nextNode->next = head; // 開始逐級返回開始後，尾變頭，原來的結點序中，後一個結點依次指向前一個結點 return reverseNode; // 每次返回都帶回原尾結點（現在的頭結點） }
三、雙參數遞歸逆置
從上一個方法中了解到遞歸逆置無非就是在逐級返回這個過程中 不斷讓後一個結點指向前一個結點。
那我們顯然可以直接將前後結點作為函數形參在遞歸過程中依次遍歷鏈表，當後結點到達尾結點時，開始逐級返回並讓後結點的next指向前結點，當然這裡需要記得在函數返回時傳遞尾結點（逆置後的頭結點）
程式碼如下
ElemSN *ReverseList(ElemSN *ptr, ElemSN *pre) { if(ptr->next == NULL || ptr == NULL){ ptr->next = pre; return ptr; } ElemSN *reverseNode = ReverseList(ptr->next, ptr); ptr->next = pre; return reverseNode; }
在這個函數中不用擔心會在尾部生成一個環，遞歸，從哪裡開始，最終又會回到哪裡，所以在調用該函數時 可以使用 head = ReverseList(head, NULL);的語句，這樣子，函數的起點狀態將是 ,ptr = head, pre = NULL,最終也會是這個狀態，所以 在最後一次返回該函數時
ptr->next = pre;相當於我們傳進去的頭指針next指向了NULL，這樣逆置後的鏈表尾部自然就是NULL了。
————————————–以下為9.6號補充——————————
再次回顧該程式碼時，發現函數的第一次返回點和函數逐級返回時的語句有重複的地方，再次思考後發現該重複點可以合併，於是就產生了下面的程式碼。（兩處分別是 return ptr;和return reverseNode;的上一條語句 ptr->next = pre;）
ElemSN *ReverseList(ElemSN *ptr, ElemSN *pre) { if(ptr == NULL){ return pre; } ElemSN *reverseNode = ReverseList(ptr->next, ptr); ptr->next = pre; return reverseNode; }
——————————————–end—————————————–
End。
