Time：2019/4/23
Title: Reverse Linked List
Difficulty: Easy
Author: 小鹿
題目：Reverse Linked List（反轉(zhuǎn)鏈表）
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）反轉(zhuǎn)鏈表的我們第一能夠想到的方法就是最常用的方法，聲明三個(gè)指針析命，把頭結(jié)點(diǎn)變?yōu)槲步Y(jié)點(diǎn)锰茉，然后下一結(jié)點(diǎn)拼接到尾結(jié)點(diǎn)的頭部萄金，一次類推涩惑。說白了就是就是直接將鏈表指針反轉(zhuǎn)就可以實(shí)現(xiàn)反轉(zhuǎn)鏈表奉呛。
▉ 算法思路
兩種方法：
- 一般反轉(zhuǎn)
- 遞歸法
一般解決：
1）定義三個(gè)指針畔勤，分別為 Pnext胯陋、pre蕊温、current，current 存儲(chǔ)當(dāng)前結(jié)點(diǎn)遏乔， pre 指向反轉(zhuǎn)好的結(jié)點(diǎn)的頭結(jié)點(diǎn)义矛，Pnext 存儲(chǔ)下一結(jié)點(diǎn)信息。
2）判斷當(dāng)前結(jié)點(diǎn)是否可以反轉(zhuǎn)（是否為空鏈表或鏈表大于 1 個(gè)結(jié)點(diǎn)）?
步驟：
1）Pnext 指針存儲(chǔ)下一結(jié)點(diǎn) 盟萨。
2）當(dāng)前結(jié)點(diǎn)的 next 結(jié)點(diǎn)是否為 null (為 null 的話當(dāng)前結(jié)點(diǎn)就是最后的一個(gè)結(jié)點(diǎn))凉翻，如果為 null，將當(dāng)前節(jié)點(diǎn)賦值為 head 頭指針（斷裂處）捻激。
3）將 pre 指針指向的結(jié)點(diǎn)賦值當(dāng)前節(jié)點(diǎn) current 的下一結(jié)點(diǎn) next制轰。
4）然后讓 pre 指針指向當(dāng)前節(jié)點(diǎn) current。
5）current 繼續(xù)遍歷, 當(dāng)前節(jié)點(diǎn)指向 current 指向 Pnext胞谭。
遞歸法（重點(diǎn)分析）：
1）先確定終止條件：當(dāng)下一結(jié)點(diǎn)為 null 時(shí)垃杖，返回當(dāng)前節(jié)點(diǎn)；
2）判斷當(dāng)前的鏈表是否為 null丈屹；
3）遞歸找到尾結(jié)點(diǎn)调俘，將其存儲(chǔ)為頭結(jié)點(diǎn)。
4）此時(shí)遞歸的層次是第二層遞歸旺垒，所以要設(shè)置為頭結(jié)點(diǎn)的下一結(jié)點(diǎn)就是當(dāng)前第二層結(jié)點(diǎn)彩库，并且將第二節(jié)點(diǎn)的下一結(jié)點(diǎn)設(shè)置為 bull。
▉ 測(cè)試用例
1）鏈表是空鏈表袖牙。
2）當(dāng)前鏈表的長(zhǎng)度小于等于 1侧巨。
3）輸入長(zhǎng)度大于 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;
}
}
▉ 性能分析
- 時(shí)間復(fù)雜度：O(n)鞭达。只需遍歷整個(gè)鏈表就可以完成反轉(zhuǎn)司忱，時(shí)間復(fù)雜度為 O(n)。
- 空間復(fù)雜度：O(1)畴蹭。只需要常量級(jí)的空間坦仍，空間復(fù)雜度為 O(1)。
歡迎一起加入到 LeetCode 開源 Github 倉庫叨襟，可以向 me 提交您其他語言的代碼繁扎。在倉庫上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開源小倉庫糊闽！
Github：https://github.com/luxiangqiang/JS-LeetCode
歡迎關(guān)注我個(gè)人公眾號(hào)：「一個(gè)不甘平凡的碼農(nóng)」梳玫，記錄了自己一路自學(xué)編程的故事。
