当前位置： 首页 > ops >正文

王道链表大题算法（部分）

ops 2025/7/2 11:11:46

一、链表的基本结构

在开始介绍算法之前，我们先定义链表的基本结构：

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 指向 nullL->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表示插入Bwhile (p != NULL) {if (flag) { // 尾插法插入Aa_tail->next = p;a_tail = p;} else { // 尾插法插入BLNode *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;
}
http://www.xdnf.cn/news/14747.html

相关文章：

  • 【记录】Word｜Word创建自动编号的多级列表标题样式
  • 每日一练：找到初始输入字符串 I
  • 企业级应用技术-ELK日志分析系统
  • 矩阵的秩 线性代数
  • 具身多模态大模型在感知与交互方面的综述
  • RabbitMQ简单消息监听
  • MongoDB 安装使用教程
  • 我认知的AI宇宙系列第三期
  • 视频讲解：门槛效应模型Threshold Effect分析数字金融指数与消费结构数据
  • 车载Tier1 supplier梳理
  • Instrct-GPT 强化学习奖励模型 Reward modeling 的训练过程原理实例化详解
  • C语言main函数的原理：程序入口的奥秘
  • 多路转接select
  • Linux云计算基础篇（2）
  • SpringCloud系列（42）--搭建SpringCloud Config分布式配置总控中心（服务端）
  • Deepoc 大模型在无人机行业应用效果的方法
  • java JNDI高版本绕过 工具介绍 自动化bypass
  • 信息安全工程师考试架构相关说明
  • Nordic空中升级OTA[NRF52832蓝牙OTA]
  • 力扣 hot100 Day30
  • Hadoop WordCount 程序实现与执行指南
  • Python 数据分析与机器学习入门 (三)：Pandas 数据导入与核心操作
  • 提示技术系列——链式提示
  • 现代 JavaScript (ES6+) 入门到实战（四）：数组的革命 map/filter/reduce - 告别 for 循环
  • stm32 USART串口协议与外设(程序)——江协教程踩坑经验分享
  • 第二届 Parloo杯 应急响应学习——畸形的爱
  • 理解 Confluent Schema Registry：Kafka 生态中的结构化数据守护者
  • Qt事件系统
  • 机器学习在智能电网中的应用：负荷预测与能源管理
  • MySQL锁机制全解析