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

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

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

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 存儲當(dāng)前結(jié)點(diǎn)， pre 指向反轉(zhuǎn)好的結(jié)點(diǎn)的頭結(jié)點(diǎn)，Pnext 存儲下一結(jié)點(diǎn)信息。
2）判斷當(dāng)前結(jié)點(diǎn)是否可以反轉(zhuǎn)（是否為空鏈表或鏈表大于 1 個(gè)結(jié)點(diǎn)）?
步驟：
1）Pnext 指針存儲下一結(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)，將其存儲為頭結(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。

▉ 測試用例

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;
       }
   }

▉ 性能分析

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

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