（OI）关于链表的学习笔记（指针 · 动态）

_Birdly_ · 2022-08-11 23:04:59 · 个人记录

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。--来自百度

链表是一种很常见的数据结构。他由两个‘域’组成：值域，指针域。本篇笔记将学习链表并做一些链表的习题。

在学习链表之前，需要熟练掌握 指针 的运用。

目录
1.单向链表
2.双向链表
3.循环链表
4.总例题
5.注意事项（易错点）

单向链表

其实单向链表并不是那么常见。因为指针域只有 next，所以在遍历或者操作时候就并没有那么灵活。对于所有类型的链表，都有两种插入方法：头插法与尾插法。

头插法

头插法就是将输入进来的结点全部插到头( head )后面。如图：

我们由此可见，头插法的核心代码如下：

s->nxt = L->nxt;
L->nxt = s->nxt;

因为是插在头的前面，所以最后输出的序列将对于输入是倒序的。

尾插法模板：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
    int data;
    LNode *nxt;
}LNode, *LinkList;
int main(){
    LinkList L, s;
    L = new LNode;
    L->nxt = NULL;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        s = new LNode;
        cin >> s->data;
        s->nxt = L->nxt;
        L->nxt = s;
    }
    LinkList p;
    p = L->nxt;
    while(p){
        cout << p->data << ' ';
        p = p->nxt;
    }
    return 0;
} 

运行结果：

In:
5
1 2 3 4 5
Out:
5 4 3 2 1

例题 (1) P1427 小鱼的数字游戏

这道题被放在数组的题单里，我们看到其实就是链表的头插法后输出结果。 Code：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
    int data;
    LNode *nxt;
}LNode, *LinkList;
int main(){
    LinkList L, s;
    L = new LNode;
    L->nxt = NULL;
    for(;;){
        s = new LNode;
        cin >> s->data;
        if(s->data == 0)
            break;
        s->nxt = L->nxt;
        L->nxt = s;
    }
    LinkList p;
    p = L->nxt;
    while(p){
        cout << p->data << ' ';
        p = p->nxt;
    }
    return 0;
} 

尾插法

尾插法就是将插入的数据都放到链的尾部。并且尾插法要比头插法多维护一个结点 tail。如图： 由此可见，尾插法核心代码如下：

R->nxt = s;
R = s;

而与头插法恰恰相反，尾插法的输出顺序相对于输入来说是顺序的。

尾插法模板：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
    int data;
    LNode *nxt;
}LNode, *LinkList;
int main(){
    LinkList L, R, s;
    L = new LNode;
    L->nxt = NULL;
    R = L;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        s = new LNode;
        cin >> s->data;
        R->nxt = s;
        R = s;
    }
    R->nxt = NULL;
    LinkList p;
    p = L->nxt;
    while(p){
        cout << p->data << ' ';
        p = p->nxt;
    }
    return 0;
} 

运行结果：

In:
5
1 2 3 4 5
Out:
1 2 3 4 5

插入

其实插入与头插法非常相像，因为头插法实则可以直接理解为在 head 与 head->nxt之间插入。如图：

由此可见，在单向链表中我们想要插入到结点 p 的前面，就要找到 p 的前驱。插入的核心代码如：

// 设 s 为要插入的结点，
// s插入 p->nxt 的前面
s->nxt = p->nxt;
p->nxt = s;

删除

同理，在单向链表的删除中，我们需要找到被删除结点的前驱。但是需要分类讨论，如果删除的是尾结点，那么直接移动尾结点。

如图：

当然，大部分情况下删除后我们为了节省内存，会将其 delete 或 free 掉。但是有时候数据仍然有用处或者数据范围小防止 RE 的话不这样也是可以的。

例题 （2） T265474 排队

明显的链表板子。 Code：

#include <bits/stdc++.h>
using namespace std;
int n, m;
typedef struct LNode{
    int data;
    LNode *nxt;
}LNode, *LinkList;
LinkList L, R, s;
void init(){
    L = new LNode;
    L->nxt = NULL;
    R = L;
    cin >> n;
    for(int i = 1; i <= n; i++){
        s = new LNode;
        cin >> s->data;
        R->nxt = s;
        R = s;
    }
    R->nxt = NULL;
}
void ins(int a, int b){
    int i = 1;
    LinkList q, p;
    q = new LNode;      q->data = b;
    for(p = L->nxt; p && i < a - 1; p = p->nxt, i++) ;
    q->nxt = p->nxt;
    p->nxt = q;
}
void del(int a){
    if(a == 1){
        LinkList p = L->nxt;
        L->nxt = p->nxt;
        free(p);
        n--;
    }
    else if(a == n){
        LinkList p;
        for(p = L->nxt; p->nxt->nxt ; p = p->nxt);
        p->nxt = NULL;
        R = p;
    }
    else {
        int i = 1;
        LinkList q, p;
        for(p = L->nxt; p && i < a - 1; p = p->nxt, i++) ;
        q = p->nxt;
        p->nxt = q->nxt;
        free(q);
    }
}
void rep(int a, int b){
    LinkList p;
    int i = 1;
    for(p = L->nxt; p && i < a; p = p->nxt, i++);
    p->data = b;
}
void outit(){
    for(LinkList p = L->nxt; p ; p = p->nxt)
        cout << p->data << ' ';
}
int main(){
    init();
    cin >> m;
    while(m--){
        int flag, a, b;
        cin >> flag;
        if(flag == 0){// 插入 
            cin >> a >> b;
            ins(a, b);
        }
        else if(flag == 1){// 删除 
            cin >> a;
            del(a);
        }
        else {// 替换 
            cin >> a >> b;
            rep(a, b);
        }
    }
    outit();
    return 0;
}

ok，单向链表的内容就此完结啦！

双向链表

双向链表与单向链表的区别就是，单向链表仅仅维护前驱，而双向链表同时维护了结点的后继。这使链表的查询、遍历等操作都会因此变得简洁、快速。（头插法、尾插法等操作不在展示全部代码）。

声明：（本笔记图画上前驱标记为 prev，原因是为了对齐美观，代码中会使用 prior 记作前驱，个人习惯，两者都有“之前，以前”的意思）。

头插法

和单向链表的头插法很像，只是要多维护一个前驱。如图：

但是我们要特判一下头结点的后继是否为空，如果是空，就不可以将 L->nxt->prior 赋值为 s。

核心代码：

// 右半部分
if(L->next)
    L->next->prior = s;
s->next = L->next;
// 左半部分
L->next = s;
s->prior = L;

尾插法

比单向链表尾插法多一步连接 s->prior 赋值 R 。如图：

核心代码：

R->nxt = s;
s->prior = R;
R = s;

插入

依旧简单。如图：

核心代码如下：

// 我们假设结点 s 插入到 p 的前面
p->prior->nxt = s;
s->nxt = p;
s->prior = p->prior;
p->prior = s;

删除

与单向链表一样，需要特判 tail。 当删除 tail 时，如图：

否则如图：

核心代码如下：

if(p == R){
    R = R->prior;
    R->nxt = NULL;
}
else {
    p->prior->nxt = p->nxt;
    p->nxt->prior = p->prior;
}

例题 P1160 队列安排

纯双向链表的板子，其中左右两边的插入的区别需要细细揣摩。

Code：

#include<bits/stdc++.h>
using namespace std;
int n, m;
typedef struct LNode{
    int ind;
    bool del;
    LNode *nxt, *prior;
}LNode, *LinkList;
LinkList L, R, s, Lst[100005];
void init(){
    L = new LNode;
    R = new LNode;
    L->nxt = L->prior = R->nxt = R->prior = NULL;
    L->ind = 0,     R->del = 0,     R->ind = 1;
    L->nxt = R, R->prior = L;
    Lst[0] = L, Lst[1] = R;
    cin >> n;
    for(int i = 2; i <= n; i++){
        int num, flag;
        s = new LNode;
        s->del = 0,     s->ind = i;
        cin >> num >> flag;
        LinkList p = Lst[num];
        if(flag == 0){
            p->prior->nxt = s;
            s->prior = p->prior;
            p->prior = s;
            s->nxt = p;
        }
        else {
            if(p != R){
                p->nxt->prior = s;
                s->nxt = p->nxt;
                s->prior = p;
                p->nxt = s;
            }
            else {
                p->nxt = s;
                s->prior = p,   s->nxt = NULL;
                R = s;
            }
        }
        Lst[i] = s;
    }
    R->nxt = NULL;
}
void del_it(LinkList p){
    if(p == R){
        R = R->prior;
        R->nxt = NULL;
    }
    else {
        p->prior->nxt = p->nxt;
        p->nxt->prior = p->prior;
    }
}
int main(){
    init();
    cin >> m;
    for(int i = 1; i <= m; i++){
        int tem;
        cin >> tem;
        if(Lst[tem]->del)
            continue;
        Lst[tem]->del = 1;
        del_it(Lst[tem]);
    }
    for(LinkList p = L->nxt; p ;p = p->nxt)
        cout << p->ind << ' ';
    cout << endl;
    return 0;
}

双向链表也完成喽！

循环链表

其实循环链表并不是那么常用，但是在特定情况下非常方便。

循环链表其实就是将一个普通的单（双）向链表的 R->nxt 赋值为 L，但是我比较习惯将 R->nxt 赋值为 L->nxt。

如图（以双向链表为例）：

而且要注意，单次遍历时候需要把条件改成 R->nxt != L->nxt 或 R->nxt != L （这个要根据你尾结点的后继连接的哪一个，看个人习惯）。

核心代码如下：

R->nxt = L->nxt;
// 或个人习惯的话改为 R->nxt = L;
L->prior = R;

例题 P1996 约瑟夫问题

相信大家都做过这个题，但是你有没有用 循环链表 做过呢？

头尾相连，非空就遍历，简直方便极了！

Code：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
    int ind;
    LNode *nxt;
}LNode, *LinkList;
LinkList L, R, s;
int main(){
    L = new LNode;
    L->nxt = NULL;      R = L;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        s = new LNode;
        s->ind = i;
        R->nxt = s;
        R = s;
    }
    R->nxt = L->nxt;
    LinkList p = L;
    while(n){
        for(int i = 1; i < m; i++)
            p = p->nxt;
        cout << p->nxt->ind << ' ';
        p->nxt = p->nxt->nxt;
        n--;
    }
    return 0;
}

循环链表也结束啦！

恭喜你，完成了对链表的基本练习，请继续阅读 总例题 部分

总例题

一些难度稍高的 链表 题目。

P4715 【深基16.例1】淘汰赛

这个题被标上了 二叉树 的标签，但是我第一次读题就知道这个题完全可以用链表做。（虽然我刚开始是用二叉树做的）。

思路：每一次比较 s 和 s->nxt， 将小的那个删除，知道确定冠军和亚军。

难点：如何实现删除结点后仍然保持 隔一个点 的遍历。

解决方法， for 循环不更改 p 的值，而是在 if 里面更改。

Code：

#include<bits/stdc++.h>
using namespace std;
int n;
typedef struct LNode{
    int data, ind;
    LNode *nxt, *prior;
}LNode, *LinkList;
LinkList L, R, s;
void del(LinkList p){
    if(p != R){
        p->nxt->prior = p->prior;
        p->prior->nxt = p->nxt;
    }
    else {
        R = R->prior;
        R->nxt = NULL;
    }
}
int main(){
    L = new LNode;
    L->nxt = L->prior = NULL;
    R = L;
    cin >> n;
    n = 1 << n;
    for(int i = 1; i <= n; i++){
        s = new LNode;
        cin >> s->data;     s->ind = i;
        R->nxt = s;
        s->prior = R;
        R = s;
    }
    R->nxt = NULL;
    while(L->nxt->nxt != R){
        for(LinkList p = L->nxt; p ; )
            if(p->data < p->nxt->data){
                del(p);
                p = p->nxt->nxt;
            }
            else {
                del(p->nxt);
                p = p->nxt;
            }
    }
    if(L->nxt->data < L->nxt->nxt->data)
        cout << L->nxt->ind;
    else cout << L->nxt->nxt->ind;
    return 0;
}

此题较水，不多介绍啦！

P7912 [CSP-J 2021] 小熊的果篮

建议这道题 3 种链表解法都打一遍，超级锻炼码力和 debug 能力。

这道题我们社团的应该都知道。。。。我的经历。。。。

刚开始我用纯链表打了，T了4个点。

思路1 60 pts：简单直白，每一次如果和上一个点不同，就输出他，然后直接删掉。

Code：

#include<bits/stdc++.h>
using namespace std;
int n, len, head = 1;
typedef struct DLNode{
    struct fruit{
        int num, ao;
    }data;
    DLNode *nxt, *prior;
}DLNode, *LinkList;
LinkList L, s, R;
void init(){
    L = new DLNode;
    L->nxt = NULL;
    R = L;
    cin >> n;
    len = n;
    for(int i = 1; i <= n; i++){
        s = new DLNode;
        scanf("%d", &s->data.ao);
        s->data.num = i;
        R->nxt = s;
        s->prior = R;
        R = s;
    }
    R->nxt = NULL;
}
void del(LinkList p){
    cout << p->data.num << ' ';
    if(len == 1)
        exit(0);
    if(p == L->nxt){
        LinkList tem = L->nxt;
        tem->nxt->prior = L;
        L = L->nxt;
        L->prior = NULL;
        free(L->prior);
    }
    else if(p == R){
        R = R->prior;
        free(R->nxt);
        R->nxt = NULL;
    }
    else {
        LinkList q;
        q = p->nxt;
        p->prior->nxt = q;
        q->prior = p->prior;
        free(p);
    }
    len--;
}
int main(){
    init();
    while(len){
        int F = 1 - L->nxt->data.ao; 
        LinkList p = L->nxt;
        for(int i = 1;p && len && i <= len; i++){
            if(p && p->data.ao != F){
                if(p != R){
                    p = p->nxt;
                    del(p->prior);
                }
                else del(p);
                F = 1 - F;
                i--;
            }
            else p = p->nxt;
        }
        cout << endl;
    }
    return 0;
}

思路2 80 pts：建立一条链，每个节点存储的是一个队列。如果队头不等于上一个结点的队头，输出队头；队空就删掉这个结点。

依然会T掉两个点，重在锻炼码力嘛。

Code：

#include<bits/stdc++.h>
using namespace std;
int a[200010], n, k;
typedef struct LNode{
    queue <int> Q;
    int kind;
    LNode *nxt, *prior;
}LNode, *LinkList;
LinkList L, R, s;
int main(){
    L = new LNode;
    L->nxt = L->prior = NULL;
    L->Q.front() = -1;
    R = L;
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ){
        s = new LNode;
        s->Q.push(i);
        s->kind = a[i];
        int j;
        for(j = i + 1 ; j <= n && a[j] == a[j - 1]; j++)
            s->Q.push(j);
        k++;
        i = j;
        R->nxt = s;
        s->prior = R;
        R = s;
    }
    R->nxt = NULL;
    while(L != R && k ){
        for(LinkList p = L->nxt; p ; p = p->nxt){
            if(p->Q.empty())        continue;
            if(p == L->nxt || p->kind != p->prior->kind){
                printf("%d ", p->Q.front());
                p->Q.pop();
            }
        }
        for(LinkList p = L->nxt; p ;p = p->nxt)
            if(p->Q.empty()){
                if(k == 1)
                    exit(0);
                if(p == L->nxt){
                    LinkList tem = L->nxt;
                    tem->nxt->prior = L;
                    L = L->nxt;
                    L->prior = NULL;
                    free(L->prior);
                }
                else if(p == R){
                    R = R->prior;
                    free(R->nxt);
                    R->nxt = NULL;
                }
                else {
                    LinkList q;
                    q = p->nxt;
                    p->prior->nxt = q;
                    q->prior = p->prior;
                    free(p);
                }
                k--;
            }
        puts("");
    }
    return 0;
}

进入漫长的思索

思路3 100 pts ：其实这道题的正解，应当维护两个链表，一个是维护块的链表，一个是维护序列的链表。详细可见这篇题解。

Code：

#include<bits/stdc++.h>
using namespace std;
int n, len, Blcnt;
typedef struct LNode{
    int data, ind;
    LNode *nxt, *prior;
}LNode, *LinkList;
typedef struct Block{
    int kind, num;
    LinkList beg, end;
    Block *nxt, *prior;
}Block, *BlockLst;
LinkList L, R, s;
BlockLst Bl, Br, Bs;
map <int, LinkList> M;
void delBlock(BlockLst p){
    if(p == Br){
        Br = p->prior;
        Br->nxt = NULL;
    }
    else {
        p->prior->nxt = p->nxt;
        p->nxt->prior = p->prior;
    }
    Blcnt --;
}
int main(){
    L = new LNode;      L->nxt = L->prior = NULL;       L->data = -1,   L->ind = 0;     R = L;
    Bl = new Block;     Bl->nxt = Bl->prior = NULL;     Bl->kind = -1;      Bl->beg = Bl->end = NULL;       Br = Bl;
    M[0] = L;
    cin >> n;
    for (int i = 1; i <= n; i++){
        s = new LNode;
        scanf("%d", &s->data);      s->ind = i;
        R->nxt = s,     s->prior = R,   R = s;
        M[i] = s;
        if(s->data != s->prior->data){
            Bs = new Block;
            Bs->beg = M[i],     Bs->kind = s->data,     Bs->num = Blcnt + 1;
            Br->nxt = Bs,   Bs->prior = Br,     Br = Bs;
            Bs->prior->end = M[i - 1];
            Blcnt ++;
        }
    }
    Br->end = M[n];
    LinkList s = new LNode;     s->ind = n + 1;
    R->nxt = s,     s->prior = R,   R = s;
    R->nxt = NULL;      Br->nxt = NULL;
    while(Blcnt){
        for(BlockLst p = Bl->nxt; p ; p = p->nxt){
            cout << p->beg->ind << ' ';
            if(p != Br)
                p->beg = p->beg->nxt;
            else {
                if(p->beg->ind <= p->end->ind && p->beg->ind < n + 1)
                    p->beg = p->beg->nxt;
            }
        }
        for(BlockLst p = Bl->nxt; p ; p = p->nxt)
            if(p->beg->ind == n + 1 || p->beg->ind > p->end->ind)
                delBlock(p);
            else if(p->kind == p->prior->kind){
                p->prior->end->nxt = p->beg;
                p->prior->end = p->end;
                delBlock(p);
            }
        cout << endl;
    }
    return 0;
}

P2234 [HNOI2002]营业额统计

这道题其实就非常考核综合实力了。

思路1 90 pts：首先，我维护了一个有序的链表，每次进入一个结点，就从后往前搜到第一个比他大于等于的结点。然后将第一个比他大于等于的结点 p 和 p->prior 判断两者哪个更加合适。如果有相等的就不插入，否则插入。

时间复杂度 ： O(n^2)

Code ：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, ans;
typedef struct LNode{
    int data;
    LNode *nxt, *prior;
}LNode, *LinkList;
LinkList L, R, s;
signed main(){
    L = new LNode;
    R = new LNode;
    L->prior = R->nxt = NULL;
    L->data = -1e9;
    cin >> n >> R->data;
    R->prior = L,   L->nxt = R,     ans = R->data;
    for(int i = 2; i <= n; i++){
        s = new LNode;
        cin >> s->data;
        for(LinkList p = R; p ; p = p->prior)
            if(p->data < s->data){
                if(p == R){
                    ans += s->data - R->data;
                    R->nxt = s, s->prior = R;
                    R = s,  R->nxt = NULL;
                }
                else {
                    int add = min(abs(p->data - s->data), abs(p->nxt->data - s->data));
                    ans += add;
                    if(add){
                        s->nxt = p->nxt;
                        p->nxt->prior = s;
                        s->prior = p;
                        p->nxt = s;
                    }
                }
                break;
            }
    }
    cout << ans;
    return 0;
}

思路2 100 pts：然后我就开始思考，如何让查找更加迅速。自然而然，我想到了二分查找。但是链表的二分查找 跳表 实在是浪费空间。我想到了桶，但是桶就不连续，无法进行二分了呀！自然，我想到了 map。

维护一个 map 用整数映射结点，其中整数便是结点的值。然后用 STL 自带的 map 中的 lower_bound 函数，刚好可以找到 第一个 大于等于 x 的位置。

（看了下题解，还没有这思路哦~~）

时间复杂度： O(nlogn)

Code：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
    int data;
    LNode *nxt, *prior;
}LNode, *LinkList;
LinkList L, R, s;       int n, ans;
map <int, LinkList> M;
int main(){
    L = new LNode;      R = new LNode;
    L->data = 2 * 1e9;
    cin >> n >> R->data;
    L->nxt = R,     R->prior = L,   R->nxt = NULL;
    M[R->data] = R,     ans = R->data;
    for(int i = 2; i <= n; i++){
        s = new LNode;
        cin >> s->data;
        if(s->data > R->data){
            ans += s->data - R->data;
            R->nxt = s;
            s->prior = R;
            R = s;
            R->nxt = NULL;
            M[s->data] = s;
        }
        else {
            map<int, LinkList> :: iterator point = M.lower_bound(s->data);
            LinkList p = point->second;
            int add = min(abs(s->data - p->data), abs(s->data - p->prior->data));
            ans += add;
            if(add){
                p->prior->nxt = s;
                s->prior = p->prior;
                p->prior = s;
                s->nxt = p;
                M[s->data] = s;
            }
        }
    }
    cout << ans;
    return 0;
}

注意事项（易错点）

1.我们通常不在头结点存放数据，当然如果你想可以。不过可以运用它存放链的长度
2.尾插法结束，如果不是循环链表，一定要让尾指针指向 NULL，否则尾指针的后继会变成迷途指针，RE。。。
3.动态链和静态链的区别与各自优缺点：
    a.动态链由指针实现，静态链由数组实现。
    b.静态链远不如动态链灵活，但动态链远不如静态链稳定。
4. 个人不是太喜欢 STL 的 list，可能因为看上去冗长？（虽然不如动态链冗长）。