链表（linked list）是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便。

单向链表

基本结构

也称为单链表，链表由若干个节点（node）构成，每个节点都包含数据域和指针域两部分。

其中，数据域就像顺序表（数组）一样储存单个数据，而指针域则指向下一个节点的地址。基本的链表节点可如下定义：

struct Node {
    int data;
    Node *next;
};

操作

插入

在节点 u 后插入元素，只需要修改 u 的 next 元素。令新插入的节点为 v，首先申请 v 的内存

void insert(Node *u, int x)
{
    Node *v = new Node;
    v->next = u->next;
    u->next = x;
}

删除

删除节点 u 后的元素，令 v = u->next，只需令 u 的 next 指向 v 的 next，然后释放 v 的内存即可。

void remove(Node *u, int x)
{
    Node *v = u->next;
    u->next = v->next;
    delete v;
}

链表的细节

数组和指针实现

在 ACM 中，链表通常有数组（静态链表）、指针两种实现方式。不同的题目中，这两种方法通常各有优劣。下面就对这两种方式进行比较。

数组

优点：

节点的编号存在时，可以和编号一一对应；
使用 unsigned 标识位置时，占用内存较小；

缺点：

编写代码时，方括号层数很多

指针

优点：

可以用箭头运算符嵌套访问：u->prev->next = u->next
已经被 delete 的节点，下一次 new 可以重新利用

缺点：

64 位机器上，指针会占 2 倍的内存
使用节点的编号时，需要用数据域额外记录
new 的常数较大

典例

链表判环

使用快慢指针。

寻找环入口

在快慢指针相遇后，将快指针移动到链表头，两指针都每次走一步，则下次与慢指针相遇就是链表入口。

（图片未公开）

思路：这个过程完全可以看作小学奥数的追及问题。约定：直线跑道长度 l，起点为 H，环长度 c，直线与环交叉点为 E，一开始 F 的速度 v_F = 2，S 的速度 v_S = 1，环上建立循环坐标，E 为原点。

让 S 和 F 最开始位于 H 点并开始运动。

当 S 进入环时，位于 E 点，\Delta t_1 = l / v_S = l，此时 F 的位置是 x_F = l \bmod c，F 与 S 距离（从 F 出发的距离）为 \Delta x = (x_S - x_F) \bmod c = (c - l) \bmod c = (-l) \bmod c；
当 S 和 F 相遇时，\Delta t_2 = \Delta x / (v_F - v_S) = (-l) \bmod c，此时坐标为 x_S' = x_F' = (0 + v_S \Delta t_2) \bmod c = (-l) \bmod c；
此时 F 被瞬间移动至 H 点，并且新速度 v_F' = 1，在 F 跑完直线跑道时，耗时 \Delta t_3 = l / v_F' = l，S 则跑到：x_S'' = (x_S' + v_S \Delta t_3) \bmod c = 0，也在 E 点，说明此时 F 和 E 恰好相遇了

注意上面论证过程中所有的关键点都是整数，这说明以上运动是对离散链表运动的插值，最终结论对链表仍然成立。

代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *p = head, *q = head;
        // p and q are fast and slow pointers
        while (p && p->next)
        {
            p = p->next->next;
            q = q->next;
            if (p == q)
            {
                break;
            }
        }
        if (!p || !(p->next))
        {
            return nullptr;
        }
        // now p moves to head, q continue to run on the ring
        p = head;
        while (p != q)
        {
            p = p->next;
            q = q->next;
        }
        // The position they meet is the entrance of the ring
        return p;
    }
};

应用场景

在 ACM 中，链表通常在需要快速删除其中部分元素，而保持其他元素顺序不变时使用。

链表一次插入和删除的时间复杂度都是 O(1)。在时间复杂度允许的情况下（如 n = 10^6），也可以使用 map 或 set 代替链表，此时时间复杂度增加到 O(\log n)。

例题

CF Edu 161 D. Berserk Monsters 模拟，使用链表快速删除