題目描述

給你單鏈表的頭節點 head ，請你反轉鏈表，並返回反轉後的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]
輸出：[2,1]

示例 3：

輸入：head = []
輸出：[]

提示：

• 鏈表中節點的數目範圍是 [0, 5000]
• -5000 <= Node.val <= 5000

進階：鏈表可以選用迭代或遞歸方式完成反轉。你能否用兩種方法解決這道題？

思路及解答

雙指針解法（迭代解法）

如果再定義一個新的鏈表，實現鏈表元素的反轉，其實這是對內存空間的浪費。

其實只需要改變鏈表的next指針的指向，直接將鏈表反轉 ，而不用重新定義一個新的鏈表，如圖所示:

之前鏈表的頭節點是元素1， 反轉之後頭結點就是元素5 ，這裏並沒有添加或者刪除節點，僅僅是改變next指針的方向。

雙指針反轉：

1. 首先定義一個cur指針，指向頭結點，再定義一個pre指針，初始化為null。
2. 開始反轉：把 cur->next 節點用tmp指針保存一下，也就是保存一下這個節點。
   為什麼要保存一下這個節點呢，因為接下來要改變 cur->next 的指向了，將cur->next 指向pre ，此時已經反轉了第一個節點了。
3. 接下來，就是循環走如下代碼邏輯了，繼續移動pre和cur指針。
4. 最後，cur 指針已經指向了null，循環結束，鏈表也反轉完畢了。 此時return pre指針就可以了，pre指針就指向了新的頭結點。

// 雙指針
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 由於單鏈表的結構，至少要用三個指針才能完成迭代反轉
        // cur 是當前遍歷的節點，pre 是 cur 的前驅結點，temp 是 cur 的後繼結點
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一個節點
            cur.next = prev;//當前節點指向prev節點
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

上面操作單鏈表的代碼邏輯不復雜，而且也不止這一種正確的寫法。但是操作指針的時候，有一些很基本、很簡單的小技巧，可以讓你寫代碼的思路更清晰：

需要注意循環的終止條件。要知道循環終止時，各個指針的位置，這樣才能保返回正確的答案。如果你覺得有點複雜想不清楚，那就動手畫一個最簡單的場景跑一下算法，比如這道題就可以畫一個只有兩個節點的單鏈表 1->2，然後就能確定循環終止後各個指針的位置了。

遞歸解法

上面的迭代解法操作指針雖然有些繁瑣，但是思路還是比較清晰的。如果現在讓你用遞歸來反轉單鏈表，有沒啥想法？對於剛開始刷題的小夥伴來説，可能很難想到，這很正常。如果有解過二叉樹系列算法題，回頭再來看這道題，就有可能有想法解這道題了。因為二叉樹結構本身就是單鏈表的延伸，相當於是二叉鏈表嘛，所以二叉樹上的遞歸思維，套用到單鏈表上是一樣的。

遞歸反轉單鏈表的關鍵在於，這個問題本身是存在子問題結構的。

例如，現在給你輸入一個以 1 為頭結點單鏈表 1->2->3->4，那麼如果忽略這個頭結點 1，只拿出 2->3->4 這個子鏈表，它也是個單鏈表對吧？

那麼這個 reverseList 函數，只要輸入一個單鏈表，就能給我反轉對吧？那麼能不能用這個函數先來反轉 2->3->4 這個子鏈表呢，然後再想辦法把 1 接到反轉後的 4->3->2 的最後面，是不是就完成了整個鏈表的反轉？

也就是

reverseList(1->2->3->4) = reverseList(2->3->4) -> 1

這就是「分解問題」的思路，通過遞歸函數的定義，把原問題分解成若干規模更小、結構相同的子問題，最後通過子問題的答案組裝原問題的解。

class Solution {
    // 定義：輸入一個單鏈表頭結點，將該鏈表反轉，返回新的頭結點
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

對於「分解問題」思路的遞歸算法，最重要的就是明確遞歸函數的定義。具體來説，我們的 reverseList 函數定義是這樣的：輸入一個節點 head，將「以 head 為起點」的鏈表反轉，並返回反轉之後的頭結點。

明白了函數的定義，再來看這個問題，這段代碼似乎就很好理解了

借用棧

借用棧先進後出的能力（或者雙端隊列，一端進，另一端出也是一樣的效果）

• 首先將所有的結點入棧
• 然後創建一個虛擬虛擬頭結點，讓cur指向虛擬頭結點。然後開始循環出棧，每出來一個元素，就把它加入到以虛擬頭結點為頭結點的鏈表當中，最後返回即可。

class Solution {  
  
    public ListNode reverseList(ListNode head) {  
        // 如果鏈表為空，則返回空  
        if (head == null) return null;  
        // 如果鏈表中只有只有一個元素，則直接返回  
        if (head.next == null) return head;  
  
        // 聲明一個雙端隊列  
        ArrayDeque<ListNode> stack = new ArrayDeque<>();  
        ListNode cur = head;  
  
        while (cur != null) {  
            stack.push(cur);  
            cur = cur.next;  
        }  
  
        // 創建一個虛擬頭結點  
        ListNode pHead = new ListNode(0);  
        cur = pHead;  
        while (!stack.isEmpty()) {  
            ListNode node = stack.pop();  
            cur.next = node;  
            cur = cur.next;  
        }  
        // 最後一個元素的next要賦值為空  
        cur.next = null;  
        return pHead.next;  
    }  
}

解法總結

最好的方式還是雙指針解法；如果數據量較大，遞歸解法和借用棧的方式都有可能導致棧溢出的情況