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

GoldenaArcher 2021-09-19 18:57:32 阅读数:816

javascript ii 搜索 删除

以單鏈錶的功能為主。

Node

class Node {

constructor(value) {

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

構造函數

class LinkedList {

constructor() {

this.head = null;
}
}

isEmpty

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

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

class LinkedList {

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

return this.head === null;
}
}

插入實現

總共有三種:

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

頭插

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

時間複雜度為 O(1)

圖解如下:

  1. 原本的鏈錶

    2 為原本的 Head

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

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

    1
    2
    3
    null
    Head
  4. 更新鏈錶的 Head

    1
    2
    3
    Head
    null
class LinkedList {

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

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

尾插

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

時間複雜度為 O ( n ) O(n) 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;
}
}

中間插入

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

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

1
2
3
4
head
null

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

斷開
連接
連接
1
2
3
4
head
null

最差情况下會使用尾差,所以這也是一個 O ( n ) O(n) 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(n) O(n) 的操作,它需要完成對鏈錶的遍曆去尋找提供的值。

另外需要注意的是,搜索可以通過 遍曆 和 遞歸的方式進行實現。便利查找的空間複雜度為 O ( 1 ) O(1) 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 ) O(1) O(1)

class LinkedList {

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

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

尾删

時間複雜度為 O ( n ) O(n) 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 ) O(n) 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 ) O(n) 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 ) O(n) 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 去保留地址,隨後對 currprev 進行翻轉操作,將其更新為 curr -> prev。一直到結束遍曆,最後更新 this.head 即可。

時間複雜度為 O(n)

  • 原鏈錶

    1
    2
    3
    4
    null
    null
    prev
    next
    curr
    head
    null
  • 進入遍曆,將 next 指向下一個結點,用以保留當前比特置。同時反轉 prevcurr

    1
    2
    3
    4
    null
    prev
    next
    curr
    head
    null

    此時鏈錶本身的結構為:

    1
    2
    3
    4
    null
    head
    null
  • 更新 prevcurr 的比特置

    1
    2
    3
    4
    null
    prev
    next
    curr
    head
    null
  • 進入下一個遍曆,更新 next 的指向

    1
    2
    3
    4
    null
    prev
    next
    curr
    head
    null
  • 繼續反轉 currprev 之間的關系

    1
    2
    3
    4
    null
    prev
    next
    curr
    head
    null

    此時鏈錶的結構為:

    1
    2
    3
    4
    null
    head
    null

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

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

    1
    2
    3
    4
    null
    prev
    head
    null
    curr
    next
  • 最後將 this.head 指向 prev,實現鏈錶的翻轉

    1
    2
    3
    4
    null
    prev
    head
    null
    curr
    next
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 個結點
版权声明:本文为[GoldenaArcher]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919185730860X.html