從LeetCode學演算法 - 72 Linked List (7)

0206. Reverse Linked List (Easy)

Question

Reverse a singly linked list.

Example:

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

分析/解題

試反轉一個單向鏈結串列。
很久以前我們嘗試解過這題的較困難的版本
(0092. Reverse Linked List II (Medium))，
不過是透過stack的輔助，這題較為簡單，
我們來嘗試不使用其他資料結構來試試看吧XD！

先舉一個簡單的例子：
head -> a -> b -> c -> d -> NIL
這個單向鏈結串列在反轉的時候應該會變成：
NIL <- head <- a <- b <- c <- d

我們可以先看head, a, b這段，
在反轉時，我們要將head的next從a改成別的指向；
但如果先改掉的話，那就喪失掉a的位置了，
所以我們需要一個tmp來記錄a的位置，
再將head的next指向到前一個node (這邊一開始是NIL)，
最後讓tmp這個node做為下一個要處理的對象。
反覆處理，最終當head是null的時候，
回傳前一個node即為新的linked list的開頭(反轉前的尾端)。

所以以迭代法的步驟上會像這樣：

先宣告一個NIL的ListNode，我們命名為prev
當head非null時，進行迴圈：
2-1. 宣告一個節點n，位置指定到head的位置
2-2. head往下走到其next
2-3. n的next位置指定成prev
2-4. 再將prev的位置指定到n
迴圈完成後回傳prev即可

1
1.  (prev=NIL) head -> a    -> b ...

1
2
2.            (n)
    (prev=NIL) head -> a    -> b ...

1
2
2-3                   (head)
     prev=NIL <- n     a    -> b ...

1
2-4  NIL      <- prev  head=a -> b ...

以第一輪的迴圈推導會如上面，讀者也可以自行嘗試推演看看。

若用遞迴的話也可以達到相同效果：

呼叫一個遞迴函式rev，將(null, head)做為參數傳入
(在rev中，參數為前一個節點prev，跟當前的節點n)
如果n為NIL的話則直接回傳prev
宣告一個tmp節點，其位置指定為n.next
再將n.next的位置指定給prev
回傳rev(n, tmp)

所以不論哪一種方式，
我們基本上都是使用宣告的節點去記錄next的部分，
再將當前的節點的next指向到prev，從而完成將鏈結反向的工作。

依此，寫成如下的程式碼：

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium限額5名優惠(額滿即截止)： https://hiskio.com/courses/319?promo_code=VE9NJQE

問卷抽書＆取得上架通知： https://pse.is/MS2J2
如果你對線上課程不放心，
也可以先來12/17(二) 我在天瓏分享的講座看看！
講座連結： https://pse.is/JS3LJ