標題:LeetCode《初級演算法》連結串列之反轉連結串列 -- JavaScript

語言: CN / TW / HK

題目

題目連結:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/

image.png

題解

考研資料結構中也會出現的題~

1、使用頭插法反轉連結串列

反轉連結串列可以直接遍歷連結串列,然後藉助一個空節點當頭節點使用頭插法來實現;

```js / * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ / * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) {

let vhead = new ListNode(null,null);
let temp;
while(head !== null) {
    temp = vhead.next;
    vhead.next = head;
    head = head.next;
    vhead.next.next = temp;
}

return vhead.next;

}; ```

2、遞迴實現

題目提示中又說了可以使用遞迴實現,我之前用 C 語言寫連結串列的題目的時候沒有想到連結串列和遞迴有這麼深厚的友誼,決定分析一下和查查資料,看看連結串列和遞迴的情誼為和濃於水;

首先我們知道遞迴主要由 遞迴體遞迴結束條件 組成,對於求解某個問題時可以將整個大問題變成一個一個邏輯相同的子問題,那麼這個問題就可能可以使用遞迴解決(漢諾塔問題是經典的可以使用遞迴實現的問題);

連結串列的結構是由一個一個的節點組成的,每個節點都是一樣的結構,所以有關連結串列的問題其天然適於使用遞迴實現;

```js / * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ / * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) {

if(head === null || head.next === null) {
    return head;
}



let rhead = reverseList(head.next); // 遞迴返回的時反轉後的連結串列的第一個節點的引用

let next = head.next; // 這是重點,next 是下面遞迴返回的連結串列的最後一個節點;
next.next = head;

head.next = null; // 這也是重點,去除反轉之前的第一個節點和第二個節點形成的環
                  //  head.next === next,next.next === head

return rhead;

}; ```

和第一種方法相比,使用了遞迴棧,空間換時間,依然是這個規律~


大家如果有更好的思路和解法,歡迎大家一起來討論啊~

這是使用 JavaScript 對 LeetCode《初級演算法》的每道題的總結和實現的其中一篇,彙總篇在這裡:

https://juejin.cn/post/7006692002125316103