面試不可不會的單鏈表反轉
- 2021 年 2 月 17 日
- 筆記
單鏈表反轉是面試中常考的一道題，這道題看起來簡單，但是能一遍寫出 bug free 的程式碼相當不容易，本文主要提供遞歸和迭代兩種解題方法，供大家參考。
題目
舉栗
為了便於理解，以 1->2->3->NULL 為栗子，如下圖示：
遞歸解法
鏈表具有天然的遞歸性，一個鏈表例如：1->2->3->NULL，可以看成以值為 1 的節點作為頭節點後面掛接一個更短的(以值為 2 的節點為頭節點)的鏈表，即1->更短的鏈表（以值為2的節點作為頭節點），同理以值為2的節點作為頭節點後面也掛接一個更更短的鏈表（以值為3的節點作為頭節點）；依次類推，如下圖示。
有了這樣的思考，鏈表反轉就可以先翻轉頭節點後面掛接的更短的鏈表，然後再在翻轉後的更短鏈表的後面掛接之前的頭節點。具體如下圖示：
Show me the Code
// C語言版本
struct ListNode* reverseList(struct ListNode* head){
/* 特判 */
if (head == NULL || head->next == NULL) {
return head;
}
/* 翻轉頭節點(節點值為 1 的節點) 後面掛接的鏈表(以節點值為 2 的節點作為頭節點) */
/* 翻轉之後變成 3->2 */
struct ListNode *node = reverseList(head->next);
/* 將頭節點(節點值為 1 的節點)掛接在翻轉之後的鏈表的後面(也就是節點值為 2 的節點的後面) */
head->next->next = head;
/* 將尾節點的下一節點置空 */
head->next = NULL;
return node;
}
#python3 版本
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
node = self.reverseList(head.next)
head.next.next = head;
head.next = None;
return node;
迭代（雙指針）解法
可以用雙指針來做，用一個指針 next 記錄當前節點的後一節點，另外一個指針 pre 記錄當前節點的前一個節點，如果當前節點是頭節點，則 pre 為空指針，還是以鏈表：1->2->3->NULL 為栗子，具體如下圖示。
Show me the Code
// C語言版本
struct ListNode* reverseList(struct ListNode* head){
/* 記錄當前節點的前一節點 */
struct ListNode* pre = NULL;
while (head != NULL) {
/* 記錄當前節點的後一節點 */
struct ListNode* next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
// go語言版本
func reverseList(head *ListNode) *ListNode {
var pre *ListNode = nil
for head != nil {
next := head.Next
head.Next = pre;
pre = head
head = next
}
return pre
}
