[JavaScript 刷題] 鏈錶II，翻轉鏈錶，搜索，按值删除

以單鏈錶的功能為主。

Node

class Node {

constructor(value) {

this.value = value;
this.next = null;
}
}

構造函數

class LinkedList {

constructor() {

this.head = null;
}
}

isEmpty

判斷鏈錶是否為空，可以通過直接判斷 head 是否為 null 進行實現。

時間複雜度為 $O(1)$

class LinkedList {

// 省略其他實現
isEmpty() {

return this.head === null;
}
}

插入實現

總共有三種：

• 在頭部插入，insertAtHead()
• 在尾部插入，insertAtTail()
• 在指定索引插入，insertAtTail()

頭插

直接新建一個新的 Node，將鏈錶原本的 Head 指向新的 Node，將鏈錶的 Head 指向新的 Node。

時間複雜度為 O(1)

圖解如下：

1. 原本的鏈錶

   2 為原本的 Head

2. 新建一個 Node 作為需要插入到鏈錶頭部的 Node。

3. 將原本的 Node 2 鏈接到新建的 Node 1 後

4. 更新鏈錶的 Head

class LinkedList {

// 省略其他實現
insertAtHead(data) {

const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
}

尾插

根據接受的參數創一個新的 Node，隨後找到鏈錶最後一個結點，更新最後一個結點的 next。

時間複雜度為 $O(n)$，找到最後一個結點需要遍曆整個鏈錶。

class LinkedList {

// 省略其他實現
insertAtTail(data) {

const newNode = new Node(data);
if (this.isEmpty()) {

return this.insertAtHead(data);
}
let curr = this.head;
while (curr.nextElement !== null) {

curr = curr.nextElement;
console.log(curr);
}
curr.nextElement = newNode;
}
}

中間插入

其實會了頭插和尾差，在中間插入的實現就很簡單了。

主要還是當索引在中間階段的時候，需要斷開原本結點之間的回路，並且創立新的回路：

2 --> 4 中的回路會斷開，轉而會變成 2 --> 3 --> 4：

最差情况下會使用尾差，所以這也是一個 $O(n)$ 的操作。

class LinkedList {

// 省略其他實現
insertAt(index, data) {

const newNode = new Node(data);
// 當往頭部插入，或者鏈錶為空時，可以直接調用已經實現的函數
if (index === 0 || this.isEmpty()) return this.insertAtHead(data);
let curr = this.head,
count = 1;
while (curr.nextElement !== null && count < index) {

count++;
curr = curr.nextElement;
}
// 這裏當插入的數據大於鏈錶的長度時，直接選擇在尾部插入。不過也可以通過拋出异常來提示錯誤
if (count < index) return this.insertAtTail(data);
const next = curr.nextElement;
curr.nextElement = newNode;
newNode.nextElement = next;
}
}

搜索

搜索同樣也是一個 $O(n)$ 的操作，它需要完成對鏈錶的遍曆去尋找提供的值。

另外需要注意的是，搜索可以通過 遍曆 和 遞歸的方式進行實現。便利查找的空間複雜度為 $O(1)$，而遞歸的空間複雜度為 O(n)。

class LinkedList {

// 省略其他實現
search(value) {

let curr = this.head;
while (curr !== null) {

if (curr.value === value) return true;
curr = curr.nextElement;
}
// 調用遞歸函數
// this.recursiveSearch(this.head, value)
return false;
}
recursiveSearch(node, value) {

if (node === null) return false;
if (node.value === value) return true;
return this.recursiveSearch(node.nextElement, value);
}
}

删除

和插入一樣，删除也有幾種不同的方式：

• 頭删
• 尾删
• 中間删除
• 按值删除

頭删

時間複雜度為 $O(1)$。

class LinkedList {

// 省略其他實現
deleteAtHead() {

if (this.isEmpty()) return false;
this.head = this.head.nextElement;
return true;
}
}

尾删

時間複雜度為 $O(n)$。

class LinkedList {

// 省略其他實現
deleteAtTail() {

if (this.isEmpty()) return false;
let curr = this.head;
while (curr.nextElement.nextElement !== null) {

curr = curr.nextElement;
}
curr.nextElement = null;
return true;
}
}

中間删除

時間複雜度為 $O(n)$。

class LinkedList {

// 省略其他實現
deleteAt(index) {

if (this.isEmpty()) return false;
let count = 1,
curr = this.head;
if (index === 0) return this.deleteAtHead();
while (count < index && curr !== null) {

curr = curr.nextElement;
count++;
}
if (curr === null) return false;
// 注意空值的問題
curr.nextElement = curr.nextElement ? curr.nextElement.nextElement : null;
return true;
}
}

按值删除

其實還是搜索的邏輯，確認搜索的值是否是需要删除的值，隨後再進行操作，時間複雜度為 $O(n)$。

class LinkedList {

// 省略其他實現
deleteBy(value) {

if (this.isEmpty()) return false;
let curr = this.head;
if (curr.value === value) {

this.head = curr.nextElement;
return true;
}
while (curr.nextElement !== null) {

if (curr.nextElement.value === value) {

curr.nextElement = curr.nextElement.nextElement;
return true;
}
curr = curr.nextElement;
}
return false;
}
}

獲取長度

有兩種方式可以實現，第一種就是通過遍曆的方式去獲取鏈錶的長度；第二種則是在保存一個鏈錶長度的變量，每次操作的時候都需要更新這個變量。

這裏就不修改之前已經寫好的代碼了，直接通過遍曆的方式獲取鏈錶的長度，時間複雜度為 $O(n)$。

class LinkedList {

// 省略其他實現
length() {

let length = 0;
let curr = this.head;
while (curr !== null) {

length++;
curr = curr.nextElement;
}
return length;
}
}

翻轉鏈錶

本質上來說還是遍曆鏈錶，這個操作需要保留 3 個變量：prev, curr, next，交替更新。

原本的順序為 prev -> curr -> next，在遍曆到 curr 時需要進行通過 next 去保留地址，隨後對 curr 和 prev 進行翻轉操作，將其更新為 curr -> prev。一直到結束遍曆，最後更新 this.head 即可。

時間複雜度為 O(n)

• 原鏈錶

• 進入遍曆，將 next 指向下一個結點，用以保留當前比特置。同時反轉 prev 和 curr

  此時鏈錶本身的結構為：

• 更新 prev 和 curr 的比特置

• 進入下一個遍曆，更新 next 的指向

• 繼續反轉 curr 與 prev 之間的關系

  此時鏈錶的結構為：

  可以看到，next 之前的結點已經實現了翻轉。

• 繼續重複這個過程一直到 curr 指向空

• 最後將 this.head 指向 prev，實現鏈錶的翻轉

class LinkedList {

// 省略其他實現
reverse() {

let prev = null,
curr = this.getHead(),
next = null;
while (curr !== null) {

next = curr.nextElement;
curr.nextElement = prev;
prev = curr;
curr = next;
}
this.head = prev;
}
}

其餘有趣的實現

也是一些常見的面試題，包括：

• 檢查鏈錶中是否存在環路 (雙指針)
• 尋找鏈錶中間的結點 (雙指針)
• 移除鏈錶中重複的數據 (哈希錶)
• 尋找兩個鏈錶的並集和交集 (哈希錶)
• 返回倒數第 N 個結點