TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)?LinkedList教程及面試

更新時(shí)間：2023年02月05日 09:28:14 作者：前端要努力QAQ

這篇文章主要為大家介紹了TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)?LinkedList教程及面試，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

1. 認(rèn)識鏈表

鏈表是一種通過指針的形式把一組存儲單元聯(lián)系在一起的數(shù)據(jù)結(jié)構(gòu)。
js 中沒有鏈表，但可以用 Object 模擬鏈表
鏈表類似于火車：有一個(gè)火車頭，火車頭會連接一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)上有乘客（類似于數(shù)據(jù)），并且這個(gè)節(jié)點(diǎn)會連接下一個(gè)節(jié)點(diǎn)，以此類推

鏈表的火車結(jié)構(gòu)：

鏈表的常見操作：

append(element)：向鏈表尾部添加一個(gè)新的項(xiàng)

insert(value, position)：向鏈表的特定位置插入一個(gè)新的項(xiàng)

get(position)：獲取對應(yīng)位置的元素

indexOf(element)：返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回 -1

update(position,element)：修改某個(gè)位置的元素

removeAt(postion)：從鏈表的特定位置移除一項(xiàng)

remove(element)：從鏈表中移除一項(xiàng)

isEmpty()：如果鏈表中不包含任何元素，返回 true，如果鏈表長度大于等于0返回false

size()：返回鏈表包含的元素個(gè)數(shù)。與數(shù)組的length屬性類似

2. 實(shí)現(xiàn)鏈表結(jié)構(gòu)的封裝

2.1 基礎(chǔ)框架 v1 版

// 1. 創(chuàng)建 Node 節(jié)點(diǎn)類
class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}
// 2. 創(chuàng)建 LinkedList 的類
class LinkedList<T> {
  private head: Node<T> | null = null;
  private size: number = 0;
  get length() {
    return this.size;
  }
}

代碼解析：

封裝一個(gè) Node 類，用于封裝每一個(gè)節(jié)點(diǎn)上的信息（包括和指向下一個(gè)節(jié)點(diǎn)的引用），它是一個(gè)泛型類
封裝一個(gè) LinkedList 類，用于表示鏈表結(jié)構(gòu)
鏈表中保存兩個(gè)屬性，
size：鏈表長度

head：鏈表中的第一個(gè)節(jié)點(diǎn)

基礎(chǔ)的框架搭建好了，我們接下來就來一個(gè)個(gè)添加方法

2.2 添加 append 方法 v2 版

向 LinkedList 添加 append(element) 方法

append 方法的作用是向鏈表尾部添加一個(gè)新的項(xiàng)

  append(value: T) {
    // 1. 根據(jù) value創(chuàng)建一個(gè)新節(jié)點(diǎn)
    const newNode = new Node(value)
    // 2. 判斷 this.head 是否為 null
    if(!this.head) {
      this.head = newNode
    } else {
      let current = this.head
      while(current.next) {
        current = current.next
      }
      // 此時(shí) current 指向最后一個(gè)節(jié)點(diǎn)
      current.next = newNode 
    }
    // 3. size++
    this.size++
  }

2.3 添加 traverse 方法 v3 版

為了方便可以看到鏈表上的每一個(gè)節(jié)點(diǎn)，我們實(shí)現(xiàn)一個(gè) traverse 方法

向 LinkedList 添加 traverse 方法

traverse 方法的作用是遍歷鏈表

  traverse() {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join("->"));
  }

測試：

const l = new LinkedList<string>();
l.append("第一個(gè)節(jié)點(diǎn)");
l.append("第二個(gè)節(jié)點(diǎn)");
l.append("第三個(gè)節(jié)點(diǎn)");
l.traverse();  // 第一個(gè)節(jié)點(diǎn)->第二個(gè)節(jié)點(diǎn)->第三個(gè)節(jié)點(diǎn)

2.4 添加 insert 方法 v4 版

向 LinkedList 添加 insert(value, position) 方法

insert方法的作用是向鏈表的特定位置插入一個(gè)新的項(xiàng)

  insert(value: T, position: number): boolean {
    // 1. 越界判斷
    if (position < 0 || position >= this.size) return false;
    // 2. 根據(jù) value 創(chuàng)建新的節(jié)點(diǎn)
    const newNode = new Node(value);
    // 3. 判斷是否需要插入頭部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;
      let previous: Node<T> | null = null;
      let index = 0;
      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      // index === position
      newNode.next = current;
      previous!.next = newNode;
    }
    return true;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
// l.insert("ddd", 0); // 插入頭部位置 ddd->aaa->bbb->ccc
// l.insert("ddd", 2); // 插入第二個(gè)位置  aaa->bbb->ddd->ccc
// l.insert("ddd", 3); // 插入尾部 aaa->bbb->ccc->ddd
l.traverse();

2.5 添加 removeAt 方法 v5 版

向 LinkedList 添加 removeAt(postion) 方法

removeAt方法的作用是從鏈表的特定位置移除一項(xiàng)

  removeAt(position: number): T | null {
    // 1. 越界判斷
    if (position < 0 || position > this.size) return null;
    // 2. 判斷是否刪除第一個(gè)節(jié)點(diǎn)
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
      let previous: Node<T> | null = null;
      let index = 0;
      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      previous!.next = current?.next ?? null;
    }
    this.size--;
    return current?.value ?? null;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
// console.log(l.removeAt(0)); // aaa
// console.log(l.removeAt(1)); // bbb
// console.log(l.removeAt(2)); // ccc
// console.log(l.removeAt(3)); // null
l.traverse();

2.6 添加 get 方法 v6 版

向 LinkedList 添加 get(postion) 方法

get方法的作用是獲取對應(yīng)位置的元素

  get(position: number): T | null {
    // 越界問題
    if (position < 0 || position >= this.size) return null;
    // 2. 查找元素
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    // index === position
    return current?.value ?? null;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
console.log(l.get(0)); // aaa
console.log(l.get(1)); // bbb
console.log(l.get(2)); // ccc
console.log(l.get(3)); // null

2.7 添加 getNode 方法 v7 版

到這里，我們發(fā)現(xiàn)上面的代碼在通過 position 獲取節(jié)點(diǎn)的邏輯上有很多重復(fù)的地方，現(xiàn)在我們通過添加 getNode 方法來重構(gòu)一下

向 LinkedList 添加 getNode(postion) 私有方法

getNode方法的作用是獲取對應(yīng)位置的節(jié)點(diǎn)

  // 封裝私有方法
  // 根據(jù) position 獲取得到當(dāng)前的節(jié)點(diǎn)
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }

有了這個(gè)方法，我們就可以對 get removeAt insert 方法進(jìn)行重構(gòu)了

對 removeAt 進(jìn)行重構(gòu)

  removeAt(position: number): T | null {
    // 1. 越界判斷
    if (position < 0 || position > this.size) return null;
    // 2. 判斷是否刪除第一個(gè)節(jié)點(diǎn)
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
-      let previous: Node<T> | null = null;
-      let index = 0;
-
-      while (index++ < position && current) {
-        previous = current;
-        current = current.next;
-      }
-      previous!.next = current?.next ?? null;
+      let previous = this.getNode(position - 1);
+      current = previous?.next ?? null;
+      previous!.next = previous?.next?.next ?? null;
    }
    this.size--;
    return current?.value ?? null;
  }

對 get 進(jìn)行重構(gòu)

  get(position: number): T | null {
    // 越界問題
    if (position < 0 || position >= this.size) return null;
    // 2. 查找元素
-    let index = 0;
-    let current = this.head;
-    while (index++ < position && current) {
-      current = current?.next;
-    }
+    let current = this.getNode(position);
    return current?.value ?? null;
  }

對 insert 進(jìn)行重構(gòu)

  insert(value: T, position: number): boolean {
    // 1. 越界判斷
    if (position < 0 || position > this.size) return false;
    // 2. 根據(jù) value 創(chuàng)建新的節(jié)點(diǎn)
    const newNode = new Node(value);
    // 3. 判斷是否需要插入頭部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
-      let current = this.head;
-      let previous: Node<T> | null = null;
-      let index = 0;
-
-      while (index++ < position && current) {
-        previous = current;
-        current = current.next;
-      }
-
-      // index === position
-      newNode.next = current;
-      previous!.next = newNode;
+      const previous = this.getNode(position - 1);
+      newNode.next = previous?.next ?? null;
+      previous!.next = newNode;
    }
    return true;
  }

測試一把，都沒問題

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
// console.log(l.removeAt(0)); // aaa
// console.log(l.removeAt(1)); // bbb
// console.log(l.removeAt(2)); // ccc
// console.log(l.removeAt(3)); // null
// console.log(l.get(0)) // aaa
// console.log(l.get(1)) // bbb
// console.log(l.get(2)) // ccc
// console.log(l.get(3)) // null
// l.insert("ddd", 0); // ddd->aaa->bbb->ccc
// l.insert("ddd", 1); // aaa->ddd->bbb->ccc
// l.insert("ddd", 2); // aaa->bbb->ddd->ccc
// l.insert("ddd", 3); // aaa->bbb->ccc->ddd
// l.insert("ddd", 4); // aaa->bbb->ccc
l.traverse();

2.8 添加 update 方法 v8 版

向 LinkedList 添加 update(position,element) 方法

update方法的作用是修改某個(gè)位置的元素

  update(value: T, position: number):boolean {
    if (position < 0 || position >= this.size) return false;
    // 獲取對應(yīng)位置的節(jié)點(diǎn)，直接更新即可
    const currentNode = this.getNode(position)
    currentNode!.value = value
    return true
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
l.traverse(); // aaa->bbb->ccc
l.update("ddd", 1); // aaa->ddd->ccc
l.traverse();

2.9 添加 indexOf 方法 v9 版

向 LinkedList 添加 indexOf(element) 方法

indexOf方法的作用是返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回 -1

  indexOf(value: T) {
    // 從第一個(gè)節(jié)點(diǎn)開始，向后遍歷
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
console.log(l.indexOf("aaa"));
console.log(l.indexOf("bbb"));
console.log(l.indexOf("ccc"));

2.10 添加 remove 方法 v10 版

向 LinkedList 添加 remove(element) 方法

remove方法的作用是從鏈表中移除一項(xiàng)

  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
l.remove('bbb')
l.traverse() // aaa->ccc

2.11 添加方法 isEmpty v11 版

向 LinkedList 添加 isEmpty() 方法

isEmpty方法的作用是如果鏈表中不包含任何元素，返回 true，如果鏈表長度大于等于 0 返回 false

  isEmpty(): boolean {
    return this.size === 0;
  }

3. 面試題一：設(shè)計(jì)鏈表

這是 Leetcode 上的第 707 道題，難度為：中等

3.1 題目描述

設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。如果要使用雙向鏈表，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的。

在鏈表類中實(shí)現(xiàn)這些功能：

get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。
addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點(diǎn)。如果index小于0，則在頭部插入節(jié)點(diǎn)。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //鏈表變?yōu)?-&gt; 2-&gt; 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //現(xiàn)在鏈表是1-&gt; 3
linkedList.get(1);            //返回3

提示：

0 <= index, val <= 1000
請不要使用內(nèi)置的 LinkedList 庫。
get, addAtHead, addAtTail, addAtIndex 和 deleteAtIndex 的操作次數(shù)不超過 2000。

3.2 解答

這道題的答案在第二章就已經(jīng)給出了，我們只需要進(jìn)行一些修改即可

class Node {
  value: number;
  next: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}
class MyLinkedList {
  private head: Node | null = null;
  private size: number = 0;
  constructor() {}
  private getNode(position: number): Node | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }
  get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let current = this.getNode(index);
    return current!.value;
  }
  addAtHead(val: number): void {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.size++;
  }
  addAtTail(val: number): void {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.getNode(this.size - 1);
      current!.next = newNode;
    }
    this.size++;
  }
  addAtIndex(index: number, val: number): void {
    if (index > this.size) return;
    if (index <= 0) {
      this.addAtHead(val);
    } else {
      const newNode = new Node(val);
      const previous = this.getNode(index - 1);
      newNode.next = previous?.next ?? null;
      previous!.next = newNode;
    }
    this.size++;
  }
  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    let current = this.head;
    if (index === 0) {
      this.head = current?.next ?? null;
    } else {
      const previous = this.getNode(index - 1);
      previous!.next = previous?.next?.next ?? null;
    }
    this.size--;
  }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：

初始化消耗 O(1)

get 消耗 O(index)

addAtHead 消耗 O(1)

addAtTail 消耗 O(n)，其中 n 為鏈表當(dāng)前長度

addAtIndex 消耗 O(index)

deleteAtIndex 消耗 O(index - 1)

空間復(fù)雜度：所有函數(shù)的單詞調(diào)用空間復(fù)雜度均為 O(1)，總體空間復(fù)雜度為 O(n)，

4. 面試題二：刪除鏈表中的節(jié)點(diǎn)

這是 Leetcode 上的第 237 道題，難度為：中等

4.1 題目描述

有一個(gè)單鏈表的 head，我們想刪除它其中的一個(gè)節(jié)點(diǎn) node。

給你一個(gè)需要?jiǎng)h除的節(jié)點(diǎn) node 。你將無法訪問第一個(gè)節(jié)點(diǎn) head。

鏈表的所有值都是唯一的，并且保證給定的節(jié)點(diǎn) node 不是鏈表中的最后一個(gè)節(jié)點(diǎn)。

刪除給定的節(jié)點(diǎn)。注意，刪除節(jié)點(diǎn)并不是指從內(nèi)存中刪除它。這里的意思是：

給定節(jié)點(diǎn)的值不應(yīng)該存在于鏈表中。
鏈表中的節(jié)點(diǎn)數(shù)應(yīng)該減少 1。
node 前面的所有值順序相同。
node 后面的所有值順序相同。

自定義測試：

對于輸入，你應(yīng)該提供整個(gè)鏈表 head 和要給出的節(jié)點(diǎn) node。node 不應(yīng)該是鏈表的最后一個(gè)節(jié)點(diǎn)，而應(yīng)該是鏈表中的一個(gè)實(shí)際節(jié)點(diǎn)。
我們將構(gòu)建鏈表，并將節(jié)點(diǎn)傳遞給你的函數(shù)。
輸出將是調(diào)用你函數(shù)后的整個(gè)鏈表。

示例 1：

輸入： head = [4,5,1,9], node = 5
輸出： [4,1,9]
解釋：指定鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9

示例 2：

輸入： head = [4,5,1,9], node = 1
輸出： [4,5,9]
解釋：指定鏈表中值為 1 的第三個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9

提示：

鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [2, 1000]
-1000 <= Node.val <= 1000
鏈表中每個(gè)節(jié)點(diǎn)的值都是唯一的
需要?jiǎng)h除的節(jié)點(diǎn) node 是鏈表中的節(jié)點(diǎn) ，且不是末尾節(jié)點(diǎn)

4.2 解答

刪除節(jié)點(diǎn)的操作我們其實(shí)之前就已經(jīng)實(shí)現(xiàn)了的，我們只要拿到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，將前一個(gè)節(jié)點(diǎn)的 next 指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即可。但是這道題有一個(gè)問題就是，我們拿不到要?jiǎng)h除前點(diǎn)的上一個(gè)節(jié)點(diǎn)。

思路：

我們可以將要?jiǎng)h除的節(jié)點(diǎn)的值賦值成它的下一個(gè)節(jié)點(diǎn)就行了，這樣就將問題從刪除某個(gè)節(jié)點(diǎn)轉(zhuǎn)換成了刪除某個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，這樣的好處就是我們能拿到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
/**
 Do not return anything, modify it in-place instead.
 */
function deleteNode(node: ListNode | null): void {
  node.val = node.next.val;
  node.next = node.next.next;
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(1)。
空間復(fù)雜度：O(1)。

5. 面試題三：反轉(zhuǎn)鏈表

這是 Leetcode 上的第 206 道題，難度為：中等

5.1 解一：棧結(jié)構(gòu)

這道題可以用棧來解決，利用棧的后進(jìn)先出的特性。

思路：先依次將數(shù)據(jù) push 進(jìn)棧中，再一次從棧中 pop 出數(shù)據(jù)，拼接 pop 出來的元素成一個(gè)新的鏈表。

function reverseList(head: ListNode | null): ListNode | null {
  // head 本身為 null 時(shí) 不需要處理
  if (head === null) return null;
  // 只有一個(gè)節(jié)點(diǎn)
  if (!head.next) return head;
  // 數(shù)組模擬棧結(jié)構(gòu)
  const stack: ListNode[] = [];
  let current: ListNode | null = head;
  while (current) {
    stack.push(current);
    current = current.next;
  }
  // 依次從棧結(jié)構(gòu)中取出元素，放到一個(gè)新的鏈表中
  const newHead: ListNode = stack.pop()!
  let newHeadCurrent = newHead
  while(stack.length) {
    const node = stack.pop()!
    newHeadCurrent.next = node
    newHeadCurrent = newHeadCurrent.next
  }
  newHeadCurrent.next = null
  return newHead
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(2n) ，n 為鏈表的長度，因?yàn)橐闅v兩次鏈表
空間復(fù)雜度：O(n)，額外需要使用棧這種結(jié)構(gòu)

5.2 解二：迭代

假設(shè)鏈表為 1 ?? 2 ?? 3 ?? 4 ?? ∅，我們想要把它改成 ∅ ?? 1 ?? 2 ?? 3 ?? 4

思路：在遍歷鏈表時(shí)，將當(dāng)前節(jié)點(diǎn)的 next 指針改為指向前一個(gè)節(jié)點(diǎn)。由于節(jié)點(diǎn)沒有引用其前一個(gè)節(jié)點(diǎn)，因此必須事先存儲其前一個(gè)節(jié)點(diǎn)。在更改引用之前，還需要存儲后一個(gè)節(jié)點(diǎn)。最后返回新的頭引用。

function reverseList(head: ListNode | null): ListNode | null {
  // 1. 判斷節(jié)點(diǎn)為 null，或者只要一個(gè)節(jié)點(diǎn)，那么直接返回即可
  if (head === null || head.next === null) return head;
  // 2. 反轉(zhuǎn)鏈表結(jié)構(gòu)
  let newHead: ListNode | null = null
  while(head) {
    const current: ListNode | null = head.next
    head.next = newHead
    newHead = head
    head = current
  }
  return newHead
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)，其中 n 是鏈表的長度。需要遍歷鏈表一次。
空間復(fù)雜度：O(1)。

5.3 解三：遞歸

遞歸版本稍微復(fù)雜一些，其關(guān)鍵在于反向工作。

思路：

假如我們有一個(gè)鏈表 1 -> 2 -> 3 -> 4

如果我們想反轉(zhuǎn) 1 <- 2 就必須先將反轉(zhuǎn) 2 <- 3，因?yàn)槿绻覀儗?1 -> 2 反轉(zhuǎn)成 1 <- 2 后，那么 2 后邊的節(jié)點(diǎn)就再也拿不到了。按照上面的邏輯遞歸，我們需要先將最后的 3 -> 4 反轉(zhuǎn)成 3 <- 4 在反轉(zhuǎn)前面的節(jié)點(diǎn)。

function reverseList(head: ListNode | null): ListNode | null {
  // 1. 判斷節(jié)點(diǎn)為 null，或者只要一個(gè)節(jié)點(diǎn)，那么直接返回即可
  if (head === null || head.next === null) {
    return head
  };
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中 n 是鏈表的長度。需要對鏈表的每個(gè)節(jié)點(diǎn)進(jìn)行反轉(zhuǎn)操作。
空間復(fù)雜度：O(n)，其中 n 是鏈表的長度?？臻g復(fù)雜度主要取決于遞歸調(diào)用的?？臻g，最多為 n 層。

以上就是TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu) LinkedList教程及面試的詳細(xì)內(nèi)容，更多關(guān)于TypeScript 鏈表結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: