一、链表基础

  • 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
  • 链接的入口节点称为链表的头结点也就是head。

二、链表类型

1、单链表

2、双链表

  • 每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
  • 双链表既可以向前查询也可以向后查询。

3、循环链表

  • 循环链表，顾名思义，就是链表首尾相连。可以用来解决约瑟夫环问题。

三、链表的存储方式

  • 链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

四、链表的操作

1、删除节点

  • 删除D节点，如图所示：
  • 只要将C节点的next指针 指向E节点就可以了。
  • 在C++里最好是再手动释放这个D节点，释放这块内存。
  • Java、Python 有自己的内存回收机制，就不用自己手动释放了。

2、添加节点

五、JS定义链表

1
2
3
4
5
6
7
8
class ListNode {
    val;
    next = null;
    constructor(value) {
        this.val = value;
        this.next = null;
    }
}

六、链表经典题目

虚拟头节点

  • 链表的一大问题就是操作当前节点必须要找前一个节点才能操作。
  • 每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
移除链表元素

链表基本操作

设计链表

反转链表

  • 两种反转的方式，迭代法和递归法。
反转链表

删除倒数第N个节点

删除倒数第N个节点

链表相交

链表相交

环形链表

链表相交