QEQuantumEinsteinSearchCtrl/⌘K
Notes/📖 数据结构（Data Structure）—— 408考研完全笔记/第二章 线性表

第二章 线性表

10 分钟阅读4,285 字17 个小节
返回目录

第二章 线性表

2.1 线性表的定义和基本操作

一、线性表的定义

线性表（Linear List）：具有相同数据类型的 nn（n≥0n \geq 0）个数据元素的有限序列，其中 nn 为表长，当 n=0n=0 时称为空表。记作：

L=(a1,a2,…,ai,…,an)L = (a_1, a_2, \ldots, a_i, \ldots, a_n)

  • a1a_1 是表头元素，ana_n 是表尾元素
  • ai−1a_{i-1} 是 aia_i 的直接前驱，ai+1a_{i+1} 是 aia_i 的直接后继
  • 除表头元素外，每个元素有且仅有一个直接前驱
  • 除表尾元素外，每个元素有且仅有一个直接后继

🗣️ 大白话：线性表就是一排相同类型的东西排成一条线。就像食堂排队，每个人前面最多一个人（前驱），后面最多一个人（后继），第一个人没有前驱（他就是排头），最后一个人没有后继（他最后一个）。

线性表的特点：

  1. 表中元素个数有限
  2. 表中元素具有逻辑上的顺序性，有先后次序
  3. 表中元素都是数据元素，每个元素都是单个元素
  4. 表中元素的数据类型都相同，每个元素占有相同大小的存储空间
  5. 表中元素具有抽象性（仅讨论逻辑关系，不考虑元素具体表示什么）

二、线性表的基本操作（9大操作）

操作功能
InitList(&L)初始化表，构造一个空的线性表
Length(L)求表长，返回线性表的长度（元素个数）
LocateElem(L, e)按值查找，在表中查找具有给定值的元素
GetElem(L, i)按位查找，获取表中第 i 个位置的元素的值
ListInsert(&L, i, e)插入操作，在第 i 个位置上插入元素 e
ListDelete(&L, i, &e)删除操作，删除第 i 个位置的元素，并返回其值
PrintList(L)输出操作，按前后顺序输出线性表所有元素值
Empty(L)判空操作，判断线性表是否为空表
DestroyList(&L)销毁操作，销毁线性表，释放内存空间

⚠️ 注意：& 表示C++中的引用，意味着函数内部对参数的修改会影响到实参。在C语言中需要使用指针实现。

2.2 顺序表（Sequential List）

一、顺序表的定义

顺序表：用顺序存储方式实现的线性表。把逻辑上相邻的元素存储在物理上也相邻的一组连续存储单元中。

随机存取特性：第 ii 个元素的地址为：

LOC(ai)=LOC(a1)+(i−1)×sizeof(ElemType)LOC(a_i) = LOC(a_1) + (i-1) \times sizeof(ElemType)

🗣️ 大白话：顺序表就是用数组存的线性表。就像宾馆房间号是连续的，知道1号房的位置和房间大小，就能直接算出第100号房的位置，不需要一个一个去找——这就是"随机存取"（也叫"直接存取"）。

🔗 【跨学科联动·计组】 顺序表的「随机存取」对应计组中 RAM（随机存取存储器） 的概念——给定地址即可在 O(1)O(1) 时间内读写。上述地址计算公式本质上就是计组中「基址 + 偏移量」的寻址方式。数组在内存中按行优先或列优先存储的规则也与计组中的存储器编址方式直接相关。

静态分配 vs 动态分配：

c
// 静态分配：数组大小固定，一旦满了就溢出
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];  // 静态数组
    int length;
} SqList;

// 动态分配：空间不足时可以重新分配更大的空间
typedef struct {
    ElemType *data;   // 动态数组的指针
    int MaxSize;
    int length;
} SeqList;
java
// 静态分配
class SqList {
    static final int MaxSize = 50;
    int[] data = new int[MaxSize];  // 静态数组
    int length;
}

// 动态分配（Java中用ArrayList更常见）
class SeqList {
    int[] data;    // 动态数组
    int maxSize;
    int length;
    SeqList(int initSize) {
        data = new int[initSize];
        maxSize = initSize;
        length = 0;
    }
}

二、顺序表的基本操作

1. 插入操作

在第 ii 个位置（1≤i≤n+11 \leq i \leq n+1）插入元素 ee，需要将第 ii 个及之后的元素后移一位。

c
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)  return false;  // 判断i的范围是否有效
    if (L.length >= MaxSize)  return false;          // 存储空间已满
    for (int j = L.length; j >= i; j--)              // 将第i个及之后元素后移
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;   // 在位置i处放入e
    L.length++;
    return true;
}
java
boolean listInsert(SqList L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= SqList.MaxSize) return false;
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}

时间复杂度分析：

  • 最好情况：在表尾插入（i=n+1i = n+1），无需移动元素，O(1)O(1)
  • 最坏情况：在表头插入（i=1i = 1），需移动 nn 个元素，O(n)O(n)
  • 平均情况：移动 n/2n/2 个元素，O(n)O(n)

2. 删除操作

删除第 ii 个位置（1≤i≤n1 \leq i \leq n）的元素，需要将第 i+1i+1 个及之后的元素前移一位。

c
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length)  return false;  // 判断i的范围是否有效
    e = L.data[i-1];       // 将被删元素赋值给e
    for (int j = i; j < L.length; j++)   // 将第i个位置后的元素前移
        L.data[j-1] = L.data[j];
    L.length--;
    return true;
}
java
boolean listDelete(SqList L, int i, int[] e) {
    if (i < 1 || i > L.length) return false;
    e[0] = L.data[i - 1];  // Java用数组模拟引用传参
    for (int j = i; j < L.length; j++)
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

时间复杂度分析：

  • 最好情况：删除表尾元素，O(1)O(1)
  • 最坏情况：删除表头元素，O(n)O(n)
  • 平均情况：O(n)O(n)

3. 查找操作

按位查找：O(1)O(1)（随机存取）

c
ElemType GetElem(SqList L, int i) {
    return L.data[i-1];  // 直接通过下标访问
}
java
int getElem(SqList L, int i) {
    return L.data[i - 1];  // 直接通过下标访问
}

按值查找（顺序查找）：O(n)O(n)

c
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)  return i + 1;  // 返回位序（从1开始）
    return 0;  // 查找失败
}
java
int locateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;
    return 0;
}

三、顺序表的特点总结

优点缺点
随机存取，O(1)O(1) 时间按位查找插入、删除需要移动大量元素
存储密度高（不需要额外指针空间）需要预先分配连续空间，不够灵活
—表的容量难以确定

🔗 【跨学科联动·计组/OS】 顺序表对应计组中的「连续存储分配」，类似 OS 中「连续内存分配」方案——优点是访问快、缺点是产生外部碎片（无法利用零散空间）。链表则类似 OS 的「链接分配」方案，不要求连续空间但需要额外指针开销。理解这对概念有助于在408四科之间融会贯通。

2.3 链表（Linked List）

一、单链表的定义

单链表：每个结点除了存放数据元素外，还存放一个指向下一个结点的指针。

c
typedef struct LNode {
    ElemType data;       // 数据域
    struct LNode *next;  // 指针域
} LNode, *LinkList;
java
class LNode {
    int data;       // 数据域
    LNode next;     // 指针域（引用下一个结点）
    LNode(int data) {
        this.data = data;
        this.next = null;
    }
}

🗣️ 大白话：单链表就像一群小朋友手拉手排队，每个人只拉着下一个人的手。你要找第5个人，必须从第1个人开始，沿着"手"一个一个摸过去。

带头结点 vs 不带头结点：

带头结点不带头结点
空表判断L->next == NULLL == NULL
优点操作统一，不需要特殊处理第一个元素节省一个结点的空间
考研常用✅ 推荐有时也会考

二、单链表的基本操作

1. 头插法建立单链表（逆序）

c
// 头插法：每次插入到头结点之后，最终顺序与输入相反
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}
java
// 头插法：每次插入到头结点之后，最终顺序与输入相反
LNode listHeadInsert(Scanner sc) {
    LNode head = new LNode(0);  // 创建头结点
    head.next = null;
    while (sc.hasNextInt()) {
        int x = sc.nextInt();
        if (x == 9999) break;
        LNode s = new LNode(x);
        s.next = head.next;
        head.next = s;
    }
    return head;
}

💡 重要应用：头插法可用于链表的逆置（原地翻转链表）！

2. 尾插法建立单链表（正序）

c
// 尾插法：每次插入到表尾，最终顺序与输入相同
LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;  // r为表尾指针
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;          // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
java
// 尾插法：每次插入到表尾，最终顺序与输入相同
LNode listTailInsert(Scanner sc) {
    LNode head = new LNode(0);  // 创建头结点
    LNode r = head;  // r为表尾指针
    while (sc.hasNextInt()) {
        int x = sc.nextInt();
        if (x == 9999) break;
        LNode s = new LNode(x);
        r.next = s;
        r = s;
    }
    r.next = null;
    return head;
}

3. 按序号查找（O(n)O(n)）

c
LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    int j = 0;
    LNode *p = L;   // p指向头结点，头结点当第0个
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}
java
LNode getElem(LNode L, int i) {
    if (i < 0) return null;
    int j = 0;
    LNode p = L;  // p指向头结点，头结点当第0个
    while (p != null && j < i) {
        p = p.next;
        j++;
    }
    return p;
}

4. 按值查找（O(n)O(n)）

c
LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}
java
LNode locateElem(LNode L, int e) {
    LNode p = L.next;
    while (p != null && p.data != e)
        p = p.next;
    return p;
}

5. 插入操作

在第 ii 个位置插入：先找到第 i−1i-1 个结点，然后插入。

c
// 在p结点之后插入s结点
s->next = p->next;
p->next = s;
java
// 在p结点之后插入s结点
s.next = p.next;
p.next = s;

在p结点之前插入（技巧：偷天换日法）：

c
// 实际是在p之后插入s，然后交换p和s的数据
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;
java
// 实际是在p之后插入s，然后交换p和s的数据
s.next = p.next;
p.next = s;
int temp = p.data;
p.data = s.data;
s.data = temp;

🗣️ 大白话：如果要在某个人前面插队，你先站到他后面，然后你俩把衣服（数据）互换一下——外人看来你就排在他前面了。

6. 删除操作

删除第 ii 个结点：先找到第 i−1i-1 个结点，然后删除。

c
// 删除p的后继结点q
q = p->next;
p->next = q->next;
free(q);
java
// 删除p的后继结点q
LNode q = p.next;
p.next = q.next;
q = null;  // Java用置空代替 free

删除结点 p 本身（技巧：用后继替自己）：

c
// 用p的后继结点的值覆盖p，然后删除后继结点
q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);
java
// 用p的后继结点的值覆盖p，然后删除后继结点
LNode q = p.next;
p.data = p.next.data;
p.next = q.next;
q = null;

三、双链表

双链表：每个结点除了后继指针外，还有一个前驱指针。

c
typedef struct DNode {
    ElemType data;
    struct DNode *prior;  // 前驱指针
    struct DNode *next;   // 后继指针
} DNode, *DLinklist;
java
class DNode {
    int data;
    DNode prior;  // 前驱指针
    DNode next;   // 后继指针
    DNode(int data) {
        this.data = data;
        this.prior = null;
        this.next = null;
    }
}

双链表插入操作（在p结点之后插入s结点）：

c
// 关键：注意赋值顺序，不能断链
s->next = p->next;       // ①
if (p->next != NULL)
    p->next->prior = s;  // ②
s->prior = p;            // ③
p->next = s;             // ④

⚠️ 顺序问题：①②必须在④之前，否则 p->next 被修改后找不到原来的后继了。

双链表删除操作（删除p的后继结点q）：

c
q = p->next;
p->next = q->next;
if (q->next != NULL)
    q->next->prior = p;
free(q);
java
// 双链表删除：删除p的后继结点q
DNode q = p.next;
p.next = q.next;
if (q.next != null)
    q.next.prior = p;
q = null;

四、循环链表

循环单链表：表尾结点的 next 指向头结点（而非 NULL），形成一个环。

  • 空表判断：L->next == L
  • 优势：从任一结点出发都能找到其他所有结点

循环双链表：头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点。

  • 空表判断：L->prior == L && L->next == L

五、静态链表

静态链表：用数组模拟链表。每个数组元素包含一个数据域和一个游标（cursor），游标充当"指针"的角色，指示下一个元素在数组中的下标。

c
#define MaxSize 50
typedef struct {
    ElemType data;
    int next;   // 下一个元素的数组下标（游标）
} SLinklist[MaxSize];
java
class SLinkNode {
    int data;
    int next;   // 下一个元素的数组下标（游标）
}
// Java中用 SLinkNode[] sLinklist = new SLinkNode[MaxSize]; 表示静态链表

🗣️ 大白话：在没有指针的语言（如早期BASIC、Fortran）中，用数组下标代替指针，模拟出链表的效果。

静态链表的特点：

  • 以 next == -1 作为链表结束标志（类似单链表的 NULL）
  • 插入和删除时只需修改游标，不需要移动元素（保留链表的优势）
  • 但容量固定，且没有顺序表的随机存取特性（查找仍需从头遍历）
  • 实际应用：操作系统的文件分配表FAT就是一种静态链表

六、顺序表 vs 链表

比较项顺序表链表
逻辑结构都属于线性表都属于线性表
存储结构顺序存储链式存储
存取方式随机存取 O(1)O(1)顺序存取 O(n)O(n)
按位查找O(1)O(1)O(n)O(n)
按值查找O(n)O(n)，有序时可折半 O(log⁡n)O(\log n)O(n)O(n)
插入删除需要移动元素 O(n)O(n)只需修改指针 O(1)O(1)（找到位置后）
空间分配需要预先分配连续空间动态分配，按需申请
存储密度高（不需要额外存储指针）低（需要额外存储指针域）
空间利用可能造成浪费（预分配多）或溢出不浪费但指针开销大
适用场景表长可预估、频繁按位查找频繁插入删除、表长难以预估

💡 选择建议：

  • 频繁查找（按位序）→ 顺序表
  • 频繁插入/删除 → 链表
  • 表长难以预估 → 链表
  • 存储空间紧张 → 顺序表（存储密度高）

📝 真题剖析

【2019年408真题】 已知一个带有表头结点的单链表，结点结构为 [data|next]。在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第 kk 个位置上的结点（kk 为正整数）。若查找成功，输出该结点的 data 值，并返回1；否则返回0。

解题方法：双指针法（快慢指针）

c
int Search_k(LinkList L, int k) {
    LNode *p = L->next, *q = L->next;
    int count = 0;
    // p指针先走k步
    while (p != NULL) {
        if (count < k)
            count++;
        else
            q = q->next;  // p走了k步后，q开始走
        p = p->next;
    }
    if (count < k) return 0;  // k超过了链表长度
    else {
        printf("%d", q->data);
        return 1;
    }
}
java
int searchK(LNode L, int k) {
    LNode p = L.next, q = L.next;
    int count = 0;
    while (p != null) {
        if (count < k)
            count++;
        else
            q = q.next;
        p = p.next;
    }
    if (count < k)
        return 0;
    else {
        System.out.println(q.data);
        return 1;
    }
}

💡 核心思路：让快指针 pp 先走 kk 步，然后 pp 和 qq 同时走。当 pp 到达表尾（NULL）时，qq 正好指向倒数第 kk 个结点。就像两个人隔着固定距离走路，前面的人到终点时，后面的人离终点恰好差那么远。

⚠️ 评分标准揭秘（2009真题原题）：一遍扫描满分15分，两遍扫描最高10分。所以一定要追求 O(n)O(n) 一遍扫描的解法！

【2010年408真题】 将 nn（n>1n>1）个整数存放到一维数组 RR 中，将 RR 中的序列循环左移 pp（0<p<n0<p<n）个位置，即由 (X0,X1,…,Xn−1)(X_0, X_1, \ldots, X_{n-1}) 变换为 (Xp,Xp+1,…,Xn−1,X0,X1,…,Xp−1)(X_p, X_{p+1}, \ldots, X_{n-1}, X_0, X_1, \ldots, X_{p-1})。要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

解题方法：三次翻转法（Reverse 法）

设计思想：将数组 abab 变为 baba（aa 代表前 pp 个元素，bb 代表后 n−pn-p 个元素）：

  1. 先将 aa 逆置得到 a−1ba^{-1}b
  2. 再将 bb 逆置得到 a−1b−1a^{-1}b^{-1}
  3. 最后将整体逆置得到 (a−1b−1)−1=ba(a^{-1}b^{-1})^{-1} = ba

例：abcdefgh 循环左移 3 位：

  • Reverse(0,2) → cba|defgh
  • Reverse(3,7) → cba|hgfed
  • Reverse(0,7) → defghabc ✓
c
void Reverse(int R[], int from, int to) {
    int temp;
    for (int i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);      // 翻转前p个
    Reverse(R, p, n - 1);      // 翻转后n-p个
    Reverse(R, 0, n - 1);      // 整体翻转
}
java
void reverse(int[] R, int from, int to) {
    for (int i = 0; i < (to - from + 1) / 2; i++) {
        int temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void converse(int[] R, int n, int p) {
    reverse(R, 0, p - 1);
    reverse(R, p, n - 1);
    reverse(R, 0, n - 1);
}

💡 三次 Reverse 的时间复杂度分别为 O(p/2)O(p/2)、O((n−p)/2)O((n-p)/2)、O(n/2)O(n/2)，合计为 O(n)O(n)，空间复杂度为 O(1)O(1)。此题是经典的空间换时间思维的反面——用巧妙的翻转避免额外空间。

【2012年408真题】 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时可共享后缀存储空间（如"loading"和"being"共享"ing"）。设 str1 和 str2 分别指向两个单词所在单链表的头结点，找出共同后缀的起始位置。

解题方法：等长对齐法

设计思想：

  1. 分别求出两个链表的长度 mm 和 nn
  2. 让较长链表的指针先走 ∣m−n∣|m-n| 步，使两个指针到表尾的距离相等
  3. 两个指针同步后移，第一次指向同一结点时即为共同后缀的起始位置
c
LinkNode* Find_1st_Common(LinkList str1, LinkList str2) {
    int len1 = Length(str1), len2 = Length(str2);
    LinkNode *p, *q;
    for (p = str1; len1 > len2; len1--)
        p = p->next;
    for (q = str2; len1 < len2; len2--)
        q = q->next;
    while (p->next != NULL && p->next != q->next) {
        p = p->next;
        q = q->next;
    }
    return p->next;
}
java
ListNode find1stCommon(ListNode str1, ListNode str2) {
    int len1 = length(str1), len2 = length(str2);
    ListNode p = str1, q = str2;
    for (; len1 > len2; len1--) p = p.next;
    for (; len1 < len2; len2--) q = q.next;
    while (p.next != null && p.next != q.next) {
        p = p.next;
        q = q.next;
    }
    return p.next;
}

💡 时间复杂度 O(m+n)O(m+n)，空间复杂度 O(1)O(1)。核心技巧：尾部对齐，同步前进。

【2011年408真题】 两个等长升序序列 AA 和 BB 各有 nn 个元素，找出 AA 和 BB 的中位数（合并后升序序列的第 ⌈n⌉\lceil n \rceil 个元素）。

解题方法：折半淘汰法

设计思想：分别取 AA、BB 的中位数 aa、bb：

  • 若 a=ba = b，则 aa 即为所求
  • 若 a<ba < b，舍弃 AA 的较小半部分和 BB 的较大半部分（保留长度相等）
  • 若 a>ba > b，舍弃 AA 的较大半部分和 BB 的较小半部分

重复上述过程，直到两序列各剩一个元素，较小者即为中位数。

💡 时间复杂度 O(log⁡2n)O(\log_2 n)，空间复杂度 O(1)O(1)。本质是二分思想的双序列应用。

⚠️ 易错点：奇数个元素时中位数所在元素需保留，偶数个元素时可舍弃中位数位置。

【2018年408真题·应用题】 给定一个含 nn 个整数的数组 A[n]，设计一个算法，找出数组中未出现的最小正整数。要求时间上尽可能高效。

设计思想：分配一个标记数组 B[n]（初始全0），扫描 A，若 0 < A[i] <= n 则令 B[A[i]-1] = 1。再扫描 B，第一个 B[i]==0 的位置即对应缺失的最小正整数 i+1；若全部为1则返回 n+1。

c
int findMissMin(int A[], int n) {
    int *B = (int *)malloc(sizeof(int) * n);
    memset(B, 0, sizeof(int) * n);
    for (int i = 0; i < n; i++)
        if (A[i] > 0 && A[i] <= n)
            B[A[i] - 1] = 1;          // 标记出现过
    for (int i = 0; i < n; i++)
        if (B[i] == 0) { free(B); return i + 1; }
    free(B);
    return n + 1;
}

💡 时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。经典的空间换时间——打标记法。

⚠️ 关键洞察：nn 个整数中，缺失的最小正整数一定在 [1,n+1][1, n+1] 范围内。

【2019年408真题·应用题】 设线性表 L=(a1,a2,…,an)L = (a_1, a_2, \ldots, a_n)（链式存储），设计就地算法将 LL 重排为 (a1,an,a2,an−1,…)(a_1, a_n, a_2, a_{n-1}, \ldots)。

设计思想（三步法）：

  1. 找中间结点：快慢指针法（fast走两步，slow走一步），slow停在中间位置
  2. 逆置后半段：将链表后半段原地逆置
  3. 交替合并：前半段与逆置后半段交替合并
c
void reorder(LinkList L) {
    // Step 1: 快慢指针找中间
    LNode *fast = L, *slow = L;
    while (fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
        if (fast->next != NULL) fast = fast->next;
    }
    // Step 2: 逆置后半段
    LNode *p = slow->next, *r;
    slow->next = NULL;
    while (p != NULL) {
        r = p->next;
        p->next = slow->next;
        slow->next = p;
        p = r;
    }
    // Step 3: 交替合并
    LNode *p1 = L->next, *p2 = slow->next, *q;
    slow->next = NULL;
    while (p2 != NULL) {
        q = p2->next;
        p2->next = p1->next;
        p1->next = p2;
        p1 = p2->next;
        p2 = q;
    }
}

💡 时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。三大经典链表子操作的综合运用：快慢指针 + 链表逆置 + 链表合并。

【2013年408真题·应用题】 已知一个整数序列 A=(a0,a1,…,an−1)A = (a_0, a_1, \ldots, a_{n-1})，其中 0≤ai<n0 \leq a_i < n（0≤i<n0 \leq i < n）。若存在 ap1=ap2=⋯=apm=xa_{p_1} = a_{p_2} = \cdots = a_{p_m} = x，且 m>n/2m > n/2（0≤pk<n0 \leq p_k < n，1≤k≤m1 \leq k \leq m），则称 xx 为 AA 的主元素。设计算法找出主元素，若存在输出该元素，否则输出 −1-1。

解题方法：Boyer-Moore 投票算法（O(n)O(n) 时间 O(1)O(1) 空间）

设计思想：

  1. 候选阶段：设 cc 为候选主元素，countcount 为计票器。遍历数组，若 count=0count = 0 则令 c=aic = a_i, count=1count = 1；否则若 ai=ca_i = c 则 countcount++，否则 countcount--。遍历结束后 cc 是"可能的主元素"。
  2. 验证阶段：再扫描一遍数组，统计 cc 实际出现次数，若 >n/2> n/2 则 cc 是主元素，否则不存在。
c
int majority(int A[], int n) {
    int c = A[0], count = 1;
    // 候选阶段
    for (int i = 1; i < n; i++) {
        if (A[i] == c) count++;
        else if (count > 0) count--;
        else { c = A[i]; count = 1; }
    }
    // 验证阶段
    count = 0;
    for (int i = 0; i < n; i++)
        if (A[i] == c) count++;
    return (count > n / 2) ? c : -1;
}
java
int majority(int[] A, int n) {
    int c = A[0], count = 1;
    // 候选阶段
    for (int i = 1; i < n; i++) {
        if (A[i] == c) count++;
        else if (count > 0) count--;
        else { c = A[i]; count = 1; }
    }
    // 验证阶段
    count = 0;
    for (int i = 0; i < n; i++)
        if (A[i] == c) count++;
    return (count > n / 2) ? c : -1;
}

💡 核心思想："多数派投票"——把不同的元素两两抵消，最后剩下的就是候选主元素。若主元素存在（占一半以上），它一定不会被完全抵消。

⚠️ 为什么需要验证阶段？ 因为当主元素不存在时（如 {1,2,3}），投票法仍会返回一个候选值（最后一个赋值的），但它不是主元素。所以必须再验证一遍。

【2020年408真题·应用题】 三个升序整数数组 A[l1]A[l_1]、B[l2]B[l_2]、C[l3]C[l_3]，找 a∈A,b∈B,c∈Ca \in A, b \in B, c \in C 使得 D=∣a−b∣+∣b−c∣+∣c−a∣D = |a-b| + |b-c| + |c-a| 最小，输出最小的 DD。

设计思想：三指针法

关键公式推导：∣a−b∣+∣b−c∣+∣c−a∣=2(max⁡(a,b,c)−min⁡(a,b,c))|a-b| + |b-c| + |c-a| = 2(\max(a,b,c) - \min(a,b,c))

证明：不妨设 a≤b≤ca \leq b \leq c，则 ∣a−b∣+∣b−c∣+∣c−a∣=(b−a)+(c−b)+(c−a)=2(c−a)=2(max⁡−min⁡)|a-b| + |b-c| + |c-a| = (b-a) + (c-b) + (c-a) = 2(c-a) = 2(\max - \min)。

因此问题转化为：最小化三者中最大值与最小值的差。

三指针策略：

  1. 三个指针分别指向三个数组的开头
  2. 每次计算 DD，更新最小值
  3. 将最小元素所在数组的指针右移（尝试缩小 max⁡−min⁡\max - \min）
  4. 当任一指针越界时停止
c
int findMinD(int A[], int l1, int B[], int l2, int C[], int l3) {
    int i = 0, j = 0, k = 0, minD = INT_MAX;
    while (i < l1 && j < l2 && k < l3) {
        int D = abs(A[i]-B[j]) + abs(B[j]-C[k]) + abs(C[k]-A[i]);
        if (D < minD) minD = D;
        // 移动最小值的指针
        int minVal = min3(A[i], B[j], C[k]);
        if (A[i] == minVal) i++;
        else if (B[j] == minVal) j++;
        else k++;
    }
    return minD;
}
java
int findMinD(int[] A, int[] B, int[] C) {
    int i = 0, j = 0, k = 0;
    int minD = Integer.MAX_VALUE;
    while (i < A.length && j < B.length && k < C.length) {
        int D = Math.abs(A[i]-B[j]) + Math.abs(B[j]-C[k]) + Math.abs(C[k]-A[i]);
        minD = Math.min(minD, D);
        int minVal = Math.min(A[i], Math.min(B[j], C[k]));
        if (A[i] == minVal) i++;
        else if (B[j] == minVal) j++;
        else k++;
    }
    return minD;
}

💡 时间复杂度 O(l1+l2+l3)O(l_1 + l_2 + l_3)，空间复杂度 O(1)O(1)。核心技巧：将绝对值之和化简为 2(max⁡−min⁡)2(\max - \min)，将三元问题转化为极差最小化问题，然后用贪心策略——每次移动最小值指针。

【2024年408真题】 带头结点的链表L，指针p指向中间的结点，执行：q=p->next; p->next=q->next; q->next=L->next; L->next=q;，功能是将p的后继结点q移动到表头（头插）。

⚠️ 链表指针操作题是选择题必考内容！解题技巧：画图模拟每一步指针变化，标注清楚修改顺序。

📌 第二章总结

核心知识点考研要求
线性表的定义与特点理解概念
顺序表的随机存取特性、地址计算公式重点
顺序表的插入、删除、查找的时间复杂度高频考点
单链表的头插法与尾插法必须掌握，大题常考
单链表的插入、删除操作（指针操作）重中之重
双链表的插入、删除（注意指针顺序）需要掌握
循环链表的特点、空表判断理解记忆
静态链表的概念了解即可
顺序表 vs 链表的比较必须掌握
链表的综合应用（双指针、链表逆置等）大题必考

典型应用：链表重排（L0→Ln→L1→Ln-1...）