付費限定文章

串列應用: 反轉整個串列Reverse Linked List_Leetcode #206_Leetcode 精選75

題目敘述

題目的輸入會給我們一個串列，要求我們從頭到尾反轉整個串列。

如果輸入是1 -> 2 -> 3，那麼輸出就是 3 -> 2 -> 1

測試範例

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

約束條件

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

進階提問

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

試著用遞迴法和迭代法去實現。

演算法

使用到double pointers 雙指針的技巧。

這邊的用法借用到sliding window 滑窗的概念

每一次迭代處理鄰近的兩個節點，改變next的方向，從指向後方轉為指向前方。這次迭代處理完，再滑動到下一組鄰近的兩個節點，用同樣的方式去反轉，一直到抵達linked list 終點為止。

遞迴、DFS演算法的精隨也在此，尋找問題共通的形式，找出共同的最小操作單元，接著用遞迴去探索整個搜索空間Search space，解出原本的問題。