一、链表的基本结构
在开始介绍算法之前，我们先定义链表的基本结构：
typedef int ElemType;
// 单链表节点结构
typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;
// 双向链表节点结构（用于访问频率调整算法）
typedef struct DNode {
ElemType data;
int freq; // 访问频率
struct DNode *pre;
struct DNode *next;
} DNode, *DLinkList;
二、习题
1. 删除值为 x 的节点
该算法实现从链表中删除所有值为 x 的节点，核心思想是通过前驱指针记录当前节点的前驱，以便在删除节点时能够正确地连接链表。
void Delete_x(LinkList &L, ElemType x) {
LNode *p = L->next, *pre = L, *m;
while (p != NULL) {
if (p->data != x) {
pre = p; // pre 记录前驱
p = pre->next;
} else {
m = p;
p = p->next;
pre->next = p; // 恢复成链
free(m);
}
}
}
2. 删除最小值节点
该算法用于删除链表中的最小值节点，核心是记录最小值节点的前驱，以便进行删除操作。
void Delete_min(LinkList &L) {
// 核心：记录最小值的前驱
if (L->next == NULL) return; // 空链表处理
LNode *pre = L, *p = L;
int mi = INT_MAX;
while (p->next != NULL) {
if (p->next->data < mi) {
pre = p;
mi = p->next->data;
}
p = p->next;
}
LNode *temp = pre->next;
pre->next = temp->next; // 越过最小值
free(temp); // 释放内存
}
3. 链表逆置
链表逆置是一个常见操作，通过头插法可以轻松实现链表的逆置。
LinkList Reverse(LinkList L) {
LNode *p, *r; // p 用来工作 r 用来保存现场
p = L->next;
L->next = NULL;
while (p != NULL) {
r = p->next; // 防止断链
p->next = L->next; // p 指向 null
L->next = p; // L作为头，后来的元素插在前面，形成逆置，接到 L 后面
p = r; // 返回继续
}
return L;
}
4. 删除指定范围内的值
删除链表中值在 [min, max] 范围内的节点，核心是保留每个节点的前驱指针。
void Delete_LR(LinkList &L, int min, int max) {
// 核心：保留每一个点的前驱
LNode *pre = L, *p = L->next;
while (p != NULL) {
if (p->data >= min && p->data <= max) { // 注意区间判断
pre->next = p->next; // 跳过符合的点，使其成为孤点
free(p); // 删除
p = pre->next; // p恢复，即原来的p->next的点
} else {
pre = p;
p = p->next;
}
}
}
5. 寻找公共节点
寻找两个链表的第一个公共节点，通过先对齐链表长度，再同时遍历的方式实现。
int find_same(LinkList L1, LinkList L2) {
LNode *p1 = L1, *p2 = L2;
int len1 = 0, len2 = 0;
// 统计L1长度
while (p1->next != NULL) {
p1 = p1->next;
len1++;
}
while (p2->next != NULL) {
p2 = p2->next;
len2++;
}
p1 = L1;
p2 = L2;
if (len1 > len2) {
while (len1 != len2) {
len1--;
p1 = p1->next;
}
} else {
while (len2 != len1) {
len2--;
p2 = p2->next;
}
}
while (p1 != p2 && p1 != NULL && p2 != NULL) { // 修正循环条件
p1 = p1->next;
p2 = p2->next;
}
if (p1 == p2 && p1 != NULL) return p1->data;
return -1;
}
6. 链表拆分
将一个链表拆分成两个链表，这里实现的是按顺序交替拆分。
void Creat_AB(LinkList C, LinkList &A, LinkList &B) {
A = (LinkList)malloc(sizeof(LNode));
B = (LinkList)malloc(sizeof(LNode));
A->next = NULL;
B->next = NULL;
LNode *p = C->next, *a_tail = A;
int flag = 1; // 1表示插入A，0表示插入B
while (p != NULL) {
if (flag) { // 尾插法插入A
a_tail->next = p;
a_tail = p;
} else { // 尾插法插入B
LNode *b_tail = B;
while (b_tail->next != NULL) b_tail = b_tail->next;
b_tail->next = p;
}
p = p->next;
flag = !flag; // 交替插入
}
a_tail->next = NULL;
LNode *b_tail = B;
while (b_tail->next != NULL) b_tail = b_tail->next;
b_tail->next = NULL;
}
7. 删除递增链表中的重复元素
对于递增有序链表，删除重复元素值，只保留一个。
void Delete_same(LinkList &L) {
LNode *p = L->next, *q;
if (p == NULL) {
return;
}
q = p->next;
while (q != NULL) {
if (p->data == q->data) {
p->next = q->next; // 提前改变
free(q); // 删除相等
q = p->next; // 防止漏删
} else {
p = q;
q = q->next;
}
}
}
8. 寻找两个有序链表的公共元素
创建一个新链表，包含两个有序链表的公共元素。
LinkList Get_Common(LinkList A, LinkList B) {
LNode *p = A->next, *q = B->next, *r, *s;
LinkList C = (LinkList)malloc(sizeof(LNode)); // 创建链表C的头节点
r = C; // r指向C的头节点，作为尾指针
while (p != NULL && q != NULL) {
if (p->data == q->data) {
s = (LNode*)malloc(sizeof(LNode));
s->data = p->data;
r->next = s;
r = s; // r成为尾节点
p = p->next;
q = q->next;
} else if (p->data < q->data) {
p = p->next;
} else {
q = q->next;
}
}
r->next = NULL;
return C;
}
9. 两链表的交集操作
保留链表 A 中同时也在链表 B 中的元素，结果存储在 A 中。
void Create_CommonList(LinkList &A, LinkList B) {
LNode *pa = A;
LNode *pb = B->next;
while (pa->next && pb) {
if (pa->next->data == pb->data) {
pa = pa->next;
pb = pb->next;
} else if (pa->next->data < pb->data) {
LNode *temp = pa->next;
pa->next = temp->next;
free(temp);
} else {
pb = pb->next; // B 小 B后移
}
}
pa->next = NULL; // 剩下的都清除
}
10. 子序列匹配
判断链表 B 是否是链表 A 的子序列。
bool string_match(LinkList A, LinkList B) {
LNode *p = A->next;
LNode *q = B->next;
LNode *start = A->next;
while (p != NULL && q != NULL) {
if (p->data == q->data) {
p = p->next;
q = q->next;
} else {
start = start->next; // 主串后移一位
p = start;
q = B->next; // 子串从头开始
}
}
return q == NULL; // 子串遍历完即匹配成功
}
12. 循环链表链接
将两个循环链表链接成一个循环链表。
LinkList Connect_List(LinkList H1, LinkList H2) {
// H1 尾接到 H2头 H2尾接到 H1头
LNode *p1 = H1;
LNode *p2 = H2;
// 找H1的尾节点
while (p1->next != H1) {
p1 = p1->next;
}
p1->next = H2->next;
// 找H2的尾节点
while (p2->next != H2) {
p2 = p2->next;
}
p2->next = H1;
return H1;
}
13. 基于访问频率的节点调整
在双向链表中，当节点被访问时，根据其访问频率调整在链表中的位置。
DLinkList Locate(DLinkList L, ElemType x) {
DNode *p = L->next;
while (p && p->data != x) p = p->next;
if (p == NULL) return NULL;
else {
p->freq++;
if (p->pre == L || p->pre->freq > p->freq) {
return p;
}
// 将 p 挪出
if (p->next != NULL) p->next->pre = p->pre;
p->pre->next = p->next;
DNode *q = p->pre;
// 利用 q 找到合适的位置
while (q != L && q->freq <= p->freq) {
q = q->pre;
}
// 将 p插入
p->next = q->next;
if (q->next != NULL) q->next->pre = p;
p->pre = q;
q->next = p;
}
return p;
}
14. 链表循环右移
将链表循环右移 k 位，通过先成环再断链的方式实现。
LinkList Converse(LinkList &L, int k) {
if (!L || !L->next) return L;
LNode *p = L;
int n = 1;
// 统计长度并成环
while (p->next != NULL) {
p = p->next;
n++;
}
p->next = L; // 变链成环
k = k % n; // 处理k大于n的情况
for (int i = 1; i <= n - k; i++) {
p = p->next; // 找新链表尾节点
}
L = p->next; // 头节点
p->next = NULL; // 断链
return L;
}
15. 检测链表是否存在环
使用快慢指针法检测链表中是否存在环，快指针每次走两步，慢指针每次走一步。
bool FindLoop(LinkList L) {
if (!L || !L->next) return false; // 空链表或单节点无环
LNode *fast = L->next, *slow = L; // 从不同位置开始，避免初始相等
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
16. 最大孪生和
对于链表，计算对称位置节点的和的最大值，适用于寻找链表中的最大孪生和。
int PairSum(LinkList L) {
if (!L || !L->next) return 0;
LNode *fast = L->next, *slow = L;
// 找中点
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
// 逆置后半部分
LNode *L2 = NULL, *p = slow->next, *temp;
while (p != NULL) {
temp = p->next;
p->next = L2;
L2 = p;
p = temp;
}
// 计算最大孪生和
int max = 0;
p = L->next;
LNode *q = L2;
while (q != NULL) {
if (p->data + q->data > max) {
max = p->data + q->data;
}
p = p->next;
q = q->next;
}
return max;
}
17. 查找倒数第 k 个节点
使用双指针法查找链表中倒数第 k 个节点，先让后指针走 k 步，然后前后指针一起走。
int last_k(LinkList L, int k) {
if (!L || !L->next) return 0;
LNode *front = L->next;
LNode *rear = L->next;
// 先让 rear 走 k步
while (k > 0) {
rear = rear->next;
k--;
if (rear == NULL) return 0; // 链表长度小于k
}
// 然后 rear front 一起走
while (rear != NULL) {
rear = rear->next;
front = front->next;
}
return front->data;
}