Time：2019/4/23
Title: Reverse Linked List
Difficulty: Easy
Author: 小鹿
題目：Reverse Linked List(反轉連結清單)
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solve:
▉ 問題分析
1)反轉連結清單的我們第一能夠想到的方法就是最常用的方法，聲明三個指針，把頭結點變為尾結點，然後下一結點拼接到尾結點的頭部，一次類推。說白了就是就是直接将連結清單指針反轉就可以實作反轉連結清單。
▉ 算法思路
兩種方法：
一般反轉
遞歸法
一般解決：
1)定義三個指針，分别為 Pnext、pre、current，current 存儲目前結點， pre 指向反轉好的結點的頭結點，Pnext 存儲下一結點資訊。
2)判斷目前結點是否可以反轉(是否為空連結清單或連結清單大于 1 個結點)?
步驟：
1)Pnext 指針存儲下一結點 。
2)目前結點的 next 結點是否為 null (為 null 的話目前結點就是最後的一個結點)，如果為 null，将目前節點指派為 head 頭指針(斷裂處)。
3)将 pre 指針指向的結點指派目前節點 current 的下一結點 next。
4)然後讓 pre 指針指向目前節點 current。
5)current 繼續周遊, 目前節點指向 current 指向 Pnext。
遞歸法(重點分析)：
1)先确定終止條件：當下一結點為 null 時，傳回目前節點；
2)判斷目前的連結清單是否為 null；
3)遞歸找到尾結點，将其存儲為頭結點。
4)此時遞歸的層次是第二層遞歸，是以要設定為頭結點的下一結點就是目前第二層結點，并且将第二節點的下一結點設定為 bull。
▉ 測試用例
1)連結清單是空連結清單。
2)目前連結清單的長度小于等于 1。
3)輸入長度大于 1 的連結清單。
▉ 遞歸法
const reverseList = (head)=>{
if(head == null || head.next == null){
return head;
}else{
let newhead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newhead;
}
}
▉ 性能分析
時間複雜度：O(n)。隻需周遊整個連結清單就可以完成反轉，時間複雜度為 O(n)。
空間複雜度：O(1)。隻需要常量級的空間，空間複雜度為 O(1)。
歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 送出您其他語言的代碼。在倉庫上堅持和小夥伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關注我個人公衆号：「一個不甘平凡的碼農」，記錄了自己一路自學程式設計的故事。