LeetCode 之 JavaScript 解答第206題 —— 反轉(zhuǎn)鏈表（Reverse Link

zhangfaliang 發(fā)布于2019-08-23 17:12 / 3548人閱讀

摘要：算法思路兩種方法一般反轉(zhuǎn)遞歸法一般解決定義三個指針，分別為，存儲當(dāng)前結(jié)點，指向反轉(zhuǎn)好的結(jié)點的頭結(jié)點，存儲下一結(jié)點信息。遞歸法重點分析先確定終止條件當(dāng)下一結(jié)點為時，返回當(dāng)前節(jié)點判斷當(dāng)前的鏈表是否為遞歸找到尾結(jié)點，將其存儲為頭結(jié)點。

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)鏈表的我們第一能夠想到的方法就是最常用的方法，聲明三個指針，把頭結(jié)點變?yōu)槲步Y(jié)點，然后下一結(jié)點拼接到尾結(jié)點的頭部，一次類推。說白了就是就是直接將鏈表指針反轉(zhuǎn)就可以實現(xiàn)反轉(zhuǎn)鏈表。

▉ 算法思路

兩種方法：

一般反轉(zhuǎn)
遞歸法

一般解決：
1）定義三個指針，分別為 Pnext、pre、current，current 存儲當(dāng)前結(jié)點， pre 指向反轉(zhuǎn)好的結(jié)點的頭結(jié)點，Pnext 存儲下一結(jié)點信息。
2）判斷當(dāng)前結(jié)點是否可以反轉(zhuǎn)（是否為空鏈表或鏈表大于 1 個結(jié)點）?
步驟：
1）Pnext 指針存儲下一結(jié)點 。
2）當(dāng)前結(jié)點的 next 結(jié)點是否為 null (為 null 的話當(dāng)前結(jié)點就是最后的一個結(jié)點)，如果為 null，將當(dāng)前節(jié)點賦值為 head 頭指針（斷裂處）。
3）將 pre 指針指向的結(jié)點賦值當(dāng)前節(jié)點 current 的下一結(jié)點 next。
4）然后讓 pre 指針指向當(dāng)前節(jié)點 current。
5）current 繼續(xù)遍歷, 當(dāng)前節(jié)點指向 current 指向 Pnext。
遞歸法（重點分析）：
1）先確定終止條件：當(dāng)下一結(jié)點為  null  時，返回當(dāng)前節(jié)點；
2）判斷當(dāng)前的鏈表是否為  null；
3）遞歸找到尾結(jié)點，將其存儲為頭結(jié)點。
4）此時遞歸的層次是第二層遞歸，所以要設(shè)置為頭結(jié)點的下一結(jié)點就是當(dāng)前第二層結(jié)點，并且將第二節(jié)點的下一結(jié)點設(shè)置為 bull。

▉ 測試用例

1）鏈表是空鏈表。

2）當(dāng)前鏈表的長度小于等于 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;
       }
   }

▉ 性能分析

時間復(fù)雜度：O(n)。只需遍歷整個鏈表就可以完成反轉(zhuǎn)，時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(1)。只需要常量級的空間，空間復(fù)雜度為 O(1)。

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關(guān)注我個人公眾號：「一個不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。