Question
206. 反轉連結清單
難度：簡單
給你 單連結清單的頭節點 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
進階：連結清單可以選用疊代或遞歸方式完成反轉。你能否用兩種方法解決這道題？
Solution
這道題總體來說有兩種思路：
先實作局部替換，進而全部替換，可以用疊代或者遞歸實作。
利用棧先進後出的特點，實作反轉
本文主要講解疊代法
在周遊連結清單時，将目前節點的 next 指針改為指向前一個節點。
由于節點沒有引用其前一個節點，是以必須事先存儲其前一個節點。
在更改引用之前，還需要存儲後一個節點。最後傳回新的頭引用。
Code
所有leetcode代碼已同步至github
歡迎star
/**
* @author yitiaoIT
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
} Result
複雜度分析
- 時間複雜度：O(N)
🌈尋寶
⭐今天是堅持刷題更文的第18/100天
⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力
⭐更多算法題歡迎關注專欄《leetcode》
為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等
怎麼領取請大家自己找，尋寶遊戲現在開始。
找不到可以評論留言，一條就會注意到你。
如果還不行，請私信我。
