嘟嘟嘟~~发车啦,快来和博主一起飙车啦!😊文末附上力扣相关题目

火车

不止图文解释,注释也很清晰噢!👍

# 1. 什么是链表

链表是一组由节点组成的集合,每个节点都有一个指针指向它的下一个节点。举个栗子来说,就像上图的小火车一样,每一节车厢之间都通过绳索相连接,每节车厢都是一个节点,车厢间的连接就是指针❤️

链表2

那了解了什么是链表之后,很多小伙伴就会想,这和数组有什么区别呢?数组操作不是更方便吗?

数组的大小是固定的,从数组的起点或中间插入或移除项的操作成本很高,因为需要移动元素(尽管我们已经学过很多的API,但背后的情况同样是这样)

# 1.1 链表的优点

相对于传统的数组,链表的一个好处在于,添加或移除元素的时候==不需要移动其他元素==。这样添加、移除操作的==时间复杂度==就为O(1)。下图就是一个单向链表插入节点的示意图,我们只需要改变前一个节点的next指针并且修改新节点的next指针是链表连接起来即可完成

链表1

# 1.2 链表的缺点

相对于数组而言,数组在访问一个元素的时候,可以直接通过索引来直接访问,而对于链表而言访问其中的一个元素,需要从起点开始迭代整个链表直到找到所需的元素。因此访问的时间复杂度落在O(1)-O(n)之间

# 1.3 单向链表与数组各个操作时间复杂度对比

链表操作 最大时间复杂度 数组操作 最大时间复杂度
search(访问) O(n) search(访问) O(1)
insert(插入) O(1) insert(插入) O(n)
remove(删除) O(1) remove(删除) O(n)
append (添加) O(1) append (添加) O(1)

# 1.4 链表的分类

有三种:单向链表、双向链表、循环链表

# 1.4.1 单向链表

链表2

# 1.4.2 双向链表

双向链表1

# 1.4.3 循环链表

循环链表单向

# 2. 使用JS实现链表

了解了什么是链表,接下来我们使用js来实现链表的相关操作

# 2.1 单向链表

# 2.1.1 创建一个单向链表

以下是一个LinkedList的基本骨架


class LinkedList {
    constructor() {
        // 链表的长度size
        this.size = 0;
        this.head = null;
    }
    //添加链表项
    append(element) { }
    //插入链表项
    appendAt(position, element) { }
    // 删除指定列表项
    remove(element) { }
    //删除指定位置链表项
    removeAt(position) { }
    // 查找指定元素索引
    indexOf(element) { }
    // 翻转链表
    reserve() { }
    // 获取节点
    getNode(index) {}
}
//测试
let l1 = new LinkedList();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

链表数据结构还需要一个Node辅助类。Node类表示要加入列表的项。它包含一个element属性,即要添加到列表的值,以及一个next属性,即指向列表中下一个节点 项的指针。

// node类
class Node {
    constructor(element) {
        this.element = element;
        // 添加一个指针
        this.next = null
    }
}
1
2
3
4
5
6
7
8

另一个重要的点是,我们还需要存储第一个节点的引用。为此,可以把这个引用存储在一个称为head的变量当中,接下来我们就要来实现LinkedList类中为填写的方法。

  • append(element) :向链表尾部添加一个新的项
  • appendAt(position, element) : 向链表的特定位置插入一个新的项
  • remove(element):从列表中移除一项
  • removeAt(position):从列表的特定位置移除一项
  • getNode(index):获取某个位置的节点
  • reserve():反转链表

# 2.1.2 获取链表中的节点

先写这个是因为后面的很多方法中都有使用到这个函数!其实也可以不用单独封装成一个函数,存粹个人习惯

传入一个需要查找的节点位置,通过for循环,不断地让current指向下一位,直至到达index的位置,跳出for循环,返回当前current节点🍊

链表迭代

getNode(index) {
    // 边界判断 传入的参数是否在链表的长度范围之内
    if (index < 0 || index >= this.size) {
        throw new Error('out')
    }
    let current = this.head;
    // 不断的让current移到下一位,直到到达index - 1位置
    // 也就是循环遍历的过程
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    // 最后返回节点
    return current
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2.1.3 向链表尾部追加元素

有两种场景:

  1. 列表为空,添加的是第一个元素
  2. 列表不为空,向其追加元素

下面是我们实现的append方法,通过上一部分的getNode方法,获取到链表的最后一个节点,让最后一个节点的next指针指向新创建的节点node,使得链表串联起来,最后让链表长度size自加,即可实现 ☘️

append(element) {
    // 通过实例化添加属性
    let node = new Node(element);
    // 添加操作
    if (this.head === null) {
        this.head = node;
    } else {
        let current = this.getNode(this.size - 1);
        // 最后一个节点的next指向新创建的节点
        current.next = node
    }
    //添加链表项后,size自增
    this.size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意:这里的节点创建是通过new操作符实现的,构造出来的node是一个对象,带有了自身的值elementnext指针,新创建的节点next指针默认指向null

# 2.1.4 向链表的任意位置插入一个元素

因为是通过位置来插入元素,所以首先要判断该位置是否越界。如果越界了,可以直接抛出错误。同样的有2种场景:

第一种场景:需要在列表的起点添加一个元素,也就是第一个位置,让新创建的节点next指针指向头节点,也就是this.head,再将新创建的节点设为头节点🎉

appendAt

第二种场景:非起点插入。首先需要找到插入位置的前一个节点pre,让新创建的节点指向pre的下一个节点pre.next,再让pre节点的next指针指向新创建的节点🍎

appendAt2

//插入链表项
appendAt(position, element) {
    // 边界判断
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    // 实例化创建节点
    let node = new Node(element);
    //起点插入
    if (position === 0) {
        node.next = this.head;
        this.head = node;
    } else {
        // 找到需要插入位置的前一个节点
        let pre = this.getNode(position - 1);
        // 让新创建的节点指向当前前一个节点的下一个节点
        node.next = pre.next;
        // 让前一个节点指向新创建的节点
        pre.next = node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 2.1.5 从链表中移除元素(根据特定位置移除)

移除元素也有两种场景:第一种是移除第一个元素,第二种是移除第一个以外的任一元素。同样的我们需要先进行边界判断,在链表长度外的抛出错误即可。🍌

第一种场景非常简单,由于移除的是第一个节点,只需要让head指向列表的第二个元素

removeAt

现在,假设我们要移除列表的最后一项或者中间某一项。首先我们需要获取到被删除节点的前一个节点,让该节点的next指针指向被删除节点的下一个节点。这样,被遗弃的元素就会被丢弃在计算机内存中,等着被垃圾回收器清除。🍐

removeAt2

//删除指定位置链表项
removeAt(position) {
    // 边界判断,超出链表长度,抛出错误
    if (position < 0 || position >= this.size) {
        throw new Error('position out range')
    }
    let current = this.head
    if (position === 0) {
        // 如果删除的是第一个节点,则让head指向下一位即可
        this.head = current.next;
    } else {
        // 获取删除位置的前一个节点
        let pre = this.getNode(position - 1); 
        // current为被删除节点
        current = pre.next;
        // 让前一个节点指向删除节点的下一个节点
        pre.next = current.next;
    }
    // 长度自减
    this.size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 2.1.6 查找元素在链表的位置

我们需要一个变量来帮助我们循环访问列表,也就是代码中的current,它的初始值是head。通过for循环来遍历链表,判断当前位置的值是否等于查找值,如果是,就返回它的位置;如果不是,就继续向下访问。如果for循环结束还未弹出,说明到达了链表的尾部,也就是说链表中不存在该元素,返回-1。💟

// 查找指定元素索引
indexOf(element) {
    // 当前链表头节点
    let current = this.head; 
    // 遍历整个链表
    for (let i = 0; i < this.size; i++) {
        if (current.element === element) {
            return i
        }
        // 依次向下移动
        current = current.next; 
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2.1.7 根据元素值移除元素

现在有了indexOf方法,我们可以传入元素的值,找到它的位置,然后调用removeAt方法并传入找到的位置,就能实现移除元素🌳

remove(element) {
    // 获取需要删除元素在链表的位置
    let index = this.indexOf(element)
    if(index!= -1 ) {
        // 通过下面的removeAt方法删除指定位置节点
        this.removeAt(index)
    }else {
        // 删除不存在的元素,抛出错误
        throw new Error('element no found')
    }
}
1
2
3
4
5
6
7
8
9
10
11

# 2.1.8 反转链表

反转链表在leetcode中经常会遇到,在各个面试题中也都会发现它的身影。所以,这里就顺带写以下

首先定义两个指针:prevcurrent,current 在前 prev 在后。每次让 currentnext指针指向prev,实现一次局部反转,局部反转完成之后,prevcurrent同时往前移动一个位置,循环这个过程,直到current到达链表尾部,实现动画如下

list

reserve() {
    let prev = null;
    let current = this.head;
    while (current) {
        // 保存当前的下一位
        let next = current.next;
        // 让当前节点指向前面的节点prev
        current.next = prev;
        // 交换完之后,让prev移到下一位也就是current
        prev = current;
        current = next;
    }
    //返回翻转的链表
    this.head = prev
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2.2 双向链表

双向链表和单向链表的区别在于,单向链表一个节点只有链向下一个节点的指针,而在双向链表中,有两个指针,一个指向前一个元素,一个指向下一个元素,示意图如下:

双向链表1

# 2.2.1 创建一个双向链表

相较于单向链表多了一个指向前一个元素的指针,所以在代码中要进行一些修改

//一个链表节点
class Node {
    constructor(element) {
        this.element = element
        this.next = null
        this.prev = null//新增
    }
}
//双向链表
class doubleLinkedList {
    constructor () {
        this.size = 0
        this.head = null
        this.tail = null//新增
    }
    // 这里是接下来写的方法
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

双向链表的优点:可以访问一个特定节点的下一个或==前一个==元素。在单向链表中,如果迭代链表时错过了要查找的元素,就需要回到链表的起点重新开始迭代😓

注意:在doubleLinedList类中有保存对列表最后一项的引用的tail属性。

# 2.2.2 获取链表中的节点

根据位置获取链表的方法和单向链表中的是相同,忘记了记得跳回去看看噢!❤️

// 获取某个位置的节点,和单向链表相同
getNode(index) {
    if (index < 0 || index >= this.size) {
        throw new Error('out')
    }
    let current = this.head
    for(let i = 0;i < index;i++) {
        current = current.next
    }
    return current
}
1
2
3
4
5
6
7
8
9
10
11

# 2.2.3 向链表尾部追加节点

相信看到这里的你,应该知道要先干嘛了吧!分两种情况

第一种情况:链表为空

第二种情况:链表不为空

对于第一种情况而言,我们只需要让headtail指向新创建的节点即可

对于第二种情况,相对于单向链表而言,有一点不一样的地方,我们需要设置前驱指针。

首先我们需要让最后一个节点的next指针指向新节点,再让新节点的prev指针指向前一个节点(也就是连接前的最后一个节点),最后记得将tail移向最后一个节点,同时size也要自增!下面是示意图,清晰明了👍

双向链表2

append(element) {
    // 创建节点
    let node = new Node(element)
    // 保存当前指向最后一个元素的指针
    let tail = this.tail
    // 如果链表为空则新节点将作为第一个
    if(this.head === null) {
        // head和tail都为node
        this.head = node
        this.tail = node
    }else {
        // 常规尾插,让最后一个元素的next指针指向node  
        tail.next = node
        // 再让node的前驱指针指向最后一个节点tail
        node.prev = tail
        // 最后更新tail指向最后一个元素node
        this.tail = node
    }
    this.size++
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 2.2.4 向链表中插入节点

向双向链表中插入一个新节点和单向链表非常相似。区别在于,单向链表只需要控制一个next指针,而双向链表则要同时控制nextprev两个指针

首先来分析第一种场景:在链表的第一个位置插入一个新节点。如果链表为空,只需要把headtail都指向这个新节点。如果不为空,current变量将保存的是链表中第一个元素的引用,那么只需让新节点的next指针指向current,让current节点的prev指针指向新节点,最后让head指向第一个节点即可,==演示过程==如下:

双向链表3

接下来是第二种场景在尾部插入,这个和上一个方法有点类似,可以查看上一小节,这里就不重复赘述了

最后一个场景也是相对复杂一点点的:在链表的中间部分插入

通过前面写的getNode方法,获取到需要插入位置的前一个节点preNode以及下一个节点current,我们将在currentpreNode元素之间插入新元素。首先,node节点的next指针指向current,再让nodeprev指针指向preNode节点,再处理剩下两个指针分别指向node即可,演示图如下:

双向链表4

// 插入节点
insert(position, element) {
    // 边界判断,输入的position需要在范围之内
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    // 创建节点
    let node = new Node(element)
    // 保存第一个节点,为一个变量
    let current = this.head
    // 第一种情况,在最头部插入
    if (position === 0) {
        // 链表为空的情况
        if (!this.head) {
            this.head = node
            this.tail = node
        } else {
            // 链表不为空
            // 让node的next指针指向第一个节点
            node.next = current
            // 第一个节点的前驱指针指向node
            current.prev = node
            // head指向新的第一个节点
            this.head = node
        }
        this.size++
    } else if (position === this.size) {
        // 在最后插入
        // current变量保存最后一个节点
        current = this.tail
        // 最后一个节点的next指针指向新节点
        current.next = node
        // 新节点的前驱指针指向前一个节点
        node.prev = current
        // tail移至node
        this.tail = node
        this.size++
    } else {
        // 在中间插入
        // 获取插入位置的前一个节点
        let preNode = this.getNode(position - 1)
        // current变量保存preNode节点的下一个节点
        current = preNode.next
        // 1. 让node节点的next指针指向后一个节点current
        node.next = current
        // 2. 让node节点的prev指针指向前一个节点preNode
        node.prev = preNode
        // 3. 让preNode节点的next指针指向新节点
        preNode.next = node
        // 4. 让current节点的prev指针指向新节点
        current.prev = node
        this.size++
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

注意:在我们封装的getNode方法中,无论如何都是从头开始遍历的,实际上我们可以优化这个过程,当我们要找的position大于size的一半时,我们可以从尾部开始遍历,这样可以提高性能。

# 2.2.5 从链表中的特定位置删除元素

双向链表的操作其实都和单向链表相似,只是多了一个前驱指针,要多操作一个指针而已,对于这个删除特定位置元素的方法,我们需要知道最重要的一点就是将被删除的节点从链表中移出,再将链表连接完好即可

同样的我们需要分成3种情况

第一种情况:删除第一个节点

current变量保存链表中第一个节点的引用,也就是我们想要移除的第一个节点。首先要改变的是 head 的引用,将其从current改为current.next。但我们还需要更新current.next指向上一个元素的指针,因此需要判断链表的长度是否为1,如果为1说明删除第一个节点之后链表就为空了,这时候就需要将tail设为null,如果不为1,则把head.prev的引用改为null即可。演示图如下:

双向链表5

第二种情况:删除最后一个节点

因为有了最后一个节点的引用tail,我们不需要通过getNode来获取最后一个节点,这样我们也就可以把tail的引用赋给current变量。接下来,需要把tail的引用更新为列表中倒数第二个元素,同时将next指针指向null,这个过程可以展示为下图:

双向链表6

第三种情况:删除中间的节点

首先我们需要通过getNode方法找到要删除的节点,用current变量保存,再用preNode表示要删除节点的前一个节点,。那么要移除它,我们可以通过更新prev.nextcurrent.next.prev的引用,在链表中跳过它,因此,将prevnext指针指向current.next,而current.nextprev指针指向prev,如下图演示:

双向链表7

removeAt(position) {
    // 边界判断,输入的position需要在范围之内
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    let current = this.head
    // 如果删除的是第一个节点
    if (position === 0) {
        // 让head指向下一位
        this.head = current.next
        // 如果链表的长度为1,删除后末尾应当为null
        if(this.size === 1) {
            this.tail = null
        }else {
            // 不为1 删除节点后第一个节点(current.next)指向null
            this.head.prev = null
        }
        this.size--
    }else if (position === this.size -1) {
        // 删除最后一个节点
        // 先让current保存我们要删除的节点
        current = this.tail
        // 让tail移向删除节点的前一位
        this.tail = current.prev
        // 再让tail的next指针指向null,这样最后一个节点就被丢弃了
        this.tail.next = null
        this.size--
    }else {
        // 被删除的节点
        let current = this.getNode(position)
        // 删除节点的前一个节点
        let preNode = current.prev
        // 删除节点的前一个节点next指向它的后一个节点
        preNode.next = current.next
        // 后一个节点的prev指向preNode
        current.next.prev = preNode
        this.size--
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 2.2.6 查找元素在链表中的位置

和单向链表的处理方式相同,没有做什么改动🍔

indexOf(element) {
    // 当前链表头节点
    let current = this.head; 
    // 遍历整个链表
    for (let i = 0; i < this.size; i++) {
        if (current.element === element) {
            return i
        }
        // 依次向下移动
        current = current.next; 
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 2.2.7 根据元素值移除节点

在前面根据位置删除链表节点的基础上,这部分的代码和单向链表相同,但也不完全相同噢,毕竟removeAt方法是一个新的方法噢!

// 根据元素值删除元素
remove(element) {
    let index = this.indexOf(element)
    if (index != -1) {
        // 通过下面的removeAt方法删除指定位置节点
        this.removeAt(index)
    } else {
        // 删除不存在的元素,抛出错误
        throw new Error('element no found')
    }
}
1
2
3
4
5
6
7
8
9
10
11

# 2.2.8 打印双向链表

通过遍历整个链表,将每个节点的值拼接起来,这样看起来会清晰很多

输出示例:NULL<->1<->2<->3<->NULL

print() {
    let str = 'NULL<->';
    let current = this.head
    while (current !== null) {
        str += current.element + '<->';
        current = current.next;
    }
    return str += 'NULL';
}
1
2
3
4
5
6
7
8
9

# 2.3 单向循环链表

循环链表和单向链表相似,节点类型都是一样,唯一的区别是,在创建循环链表的时候,需要让其最后一个节点的 next 指针指向第一个节点

// 假定lastItem为最后一个节点
lastItem.next = this.head
1
2

循环链表单向

# 2.3.1 创建一个单向循环链表

大体的结构和单向链表一致

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
class CircleLinkedList {
    constructor() {
        this.size = 0
        this.head = null
    }
    // 在末尾添加节点
    append(element) {}
    // 在任意位置插入节点
    insert(position,element) {}
    // 根据位置删除节点
    removeAt(position){}
    // 查找元素对应索引,与单向链表相同
    indexOf(element) {}
    // 根据元素值删除节点,与单向链表相同
    remove(element) {}
    // 获取节点,与单向链表相同
    getNode(index) {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 2.3.2 在链表尾部追加节点

第一种情况:链表为空,直接让head指向新节点node即可

第二种情况:链表不为空,通过getNode方法获取到链表的最后一个节点,让该节点的next指针指向新节点node

注意:在执行完if判断后都需要将最后一个节点的next指针指向第一个节点head

append(element) {
    // 创建节点
    let node = new Node(element)
    // 链表为空情况
    if (this.head === null) {
        this.head = node
    } else {
        // 获取最后一个节点
        let current = this.getNode(this.size - 1)
        current.next = node
    }
    // 不管哪种情况,都要保持首尾相连
    node.next = this.head
    this.size++
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2.3.3 在链表中插入节点

同样的有==两种场景==

  • 当插入的位置是第一个时,不同于单向链表的操作是,需要额外的将链表的最后一个节点的next指针指向新节点node
  • 在其他地方插入时,可以通过三元运算符来判断,新节点的next指向是不是null如果是null说明新节点插在最后一个节点,需要将该节点的next指针指向第一个节点,否则就正常插入即可
insert(position, element) {
    // 边界判断
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    // 实例化创建节点
    let node = new Node(element);
    if (position === 0) {
        // node指向先前的第一个节点
        node.next = this.head;
        // 头节点改变为新节点node
        this.head = node;
        let current = this.getNode(this.size - 1)
        current.next = this.head
        this.size++
    } else {
        // 找到需要插入位置的前一个节点
        let prev = this.getNode(position - 1);
        // 如果prev.next 为null就指向head否则就指向下一个
        node.next = prev.next == null ? this.head : prev.next
        // 让前一个节点指向新创建的节点
        prev.next = node;
        this.size++
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 2.3.4 在链表中删除特定位置的节点

区别于单向链表,==删除第一个节点时==,需要改变最后一个节点的next指向,指向新的第一个节点,删除其他节点时,需要判断以下被删除节点的前一个节点的next指向是否为null从而进行下一步的操作

// 根据位置删除节点
removeAt(position) {
    // 边界判断,超出链表长度,抛出错误
    if (position < 0 || position >= this.size) {
        throw new Error('position out range')
    }
    let current = this.head
    if (position === 0) {
        // 如果删除的是第一个节点,则让head指向下一位即可
        let last = this.getNode(this.size - 1); 
        this.head = current.next;
        last.next = this.head
    } else {
        // 获取删除位置的前一个节点
        let pre = this.getNode(position - 1); 
        // current为被删除节点
        current = pre.next;
        // 让前一个节点指向删除节点的下一个节点
        pre.next = current.next == null ? this.head : current.next;
    }
    // 长度自减
    this.size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 2.4 双向循环链表

双向循环链表区别于单向循环链表,双向链表有多一个从第一个节点指向最后一个节点的prev指针

双向循环链表

双向循环链表与前面的差别都不是很大,本文就不展开写了,相信看了前面的详解,一定能够自己完成的

# 3. 相关题目

leetcode上关于链表的几道题目,附上ac代码

# 3.1 反转链表 (opens new window)(链接直达噢!)

111

var reverseList = function(head) {
    let prev = null;
    let current = head;
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev
};
1
2
3
4
5
6
7
8
9
10
11

# 3.2 合并K个升序链表 (opens new window)

222

var mergeKLists = function (lists) {
    if (!lists || !lists.length) return null;
    let end = lists[0]
    let i = 1;
    while (i != lists.length) {
        end = mergeTwoLists(lists[i++], end)
    }
    return end
};

function mergeTwoLists(l1, l2) {
    // 如果其中一个为空,直接返回另一个链表
    if (!l1) return l2
    if (!l2) return l1
    // 依次比较链表的值
    if (l1.val > l2.val) {
        // 如果l2的值大,则从l2开始,l2的next通过递归再次判断是谁 
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    } else {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 3.3 删除链表的倒数第 N 个结点 (opens new window)

333

var removeNthFromEnd = function (head, n) {
    let node = head;
    let count = 0 ;
    //计算链表长度
    while(node) {
        node = node.next;
        count++;
    }
    count = count - n - 1
    if(count == -1) {
        return head.next
    }else {
        node = head;
        while(count > 0) {
        node = node.next;
        count--;
    }
    }
    node.next = node.next.next
    return head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 4. 小结

以上就是本文JavaScript实现链表的全部内容了,希望你能从中学到好多好多东西噢~❤️

今天的分享就到这里结束啦!

参考文献:javascript数据结构与算法

lastUpdate: 5/22/2022, 4:34:51 PM