【链表复习】C++ 链表复习及题目解析 (3)

article/2025/8/25 14:13:48

目录

剑指offer 中的链表题目

JZ6 从尾到头打印链表

JZ18 删除链表的结点

JZ24 反转链表

JZ25 合并两个排序的链表

JZ52 两个链表的第一个公共结点

JZ23 链表中环的入口结点

JZ22 链表中倒数第k 个结点

JZ35 复杂链表的复制

JZ76 删除链表中重复的结点

本次给大家带来所有的在剑指Offer 中的题目，请大家在学习之余也复习一下链表的相关知识。

剑指offer 中的链表题目

JZ6 从尾到头打印链表

思路：

我们都知道链表无法逆序访问，那肯定无法直接遍历链表得到从尾到头的逆序结果。但是我们都知道递归是到达底层后才会往上回溯，因此我们可以考虑递归遍历链表，因此三段式如下：

  • 终止条件： 递归进入链表尾，即节点为空节点时结束递归。

  • 返回值： 每次返回子问题之后的全部输出。

  • 本级任务： 每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾。

具体做法：

  • step 1：从表头开始往后递归进入每一个节点。

  • step 2：遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。

  • step 3：直到递归返回表头。

解法1:

 void _printListFromTailToHead(ListNode* head, vector<int>& res){if(head) {_printListFromTailToHead(head->next, res);res.push_back(head->val);}}vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;_printListFromTailToHead(head, res);return res;}

解法2:

我先从前往后迭代，而后反转链表，也可以。

 /*** struct ListNode {*       int val;*       struct ListNode *next;*       ListNode(int x) :*             val(x), next(NULL) {*       }* };*/class Solution {public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> ret;while(head){ret.push_back(head->val);head = head->next;}int n = ret.size();int left = 0, right = n - 1;while(left < right){int tmp = ret[left];ret[left] = ret[right];ret[right] = tmp;left++, right--;}return ret;}};​

解法3: 使用栈 先正序把val 输入到栈中，然后取栈顶元素放入vector中。

JZ18 删除链表的结点

 /*** struct ListNode {*int val;*struct ListNode *next;*ListNode(int x) : val(x), next(nullptr) {}* };*/class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param val int整型 * @return ListNode类*/ListNode* deleteNode(ListNode* head, int val) {if(!head) return nullptr;// write code hereListNode* newHead = new ListNode(-1);newHead->next = head;for(ListNode* node = newHead; node->next ; node = node->next){if(node->next->val == val) node->next = node->next->next;}return newHead->next;}};

JZ24 反转链表

链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。

 /*** struct ListNode {*int val;*struct ListNode *next;*ListNode(int x) : val(x), next(nullptr) {}* };*/class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code herestack<ListNode*> s;while(head){s.push(head);head = head->next;}ListNode* newHead = new ListNode(-1);ListNode* node = newHead;while(!s.empty()){ListNode* top = s.top();node->next = top;top->next = nullptr;node = top;s.pop();}return newHead->next;}};​

双指针解法：

 /*struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:ListNode* ReverseList(ListNode* pHead) {if(!pHead || !pHead->next){return pHead;}ListNode* curr = pHead;ListNode* prev = nullptr;while(curr){ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}};

JZ25 合并两个排序的链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：升序排列的方法就是比较两个链表的结点中val 的大小，取小的一个尾插到新链表中。注意在这题中可以使用虚拟头结点来简化过程。

我的解法1：

 class Solution {public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* pcurr1 = list1;ListNode* pcurr2 = list2;ListNode* head = new ListNode;ListNode* newCurr = head;while(pcurr1 && pcurr2){if(pcurr1->val > pcurr2->val){newCurr->next = pcurr2;pcurr2 = pcurr2->next;}else{newCurr->next = pcurr1;pcurr1 = pcurr1->next;}newCurr = newCurr->next;}//来判断到底是谁终止了，直接修改newCurr 到未终止的结点的指向即可。newCurr->next = (pcurr1 == nullptr) ? pcurr2 : pcurr1;return head->next;}};

我的解法2: 递归如果 list1 或者 list2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 list1 和 list2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

 class Solution {public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1)  return list2;else if(!list2) return list1;else if(list1->val < list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list1, list2->next);return list2;}}};

JZ52 两个链表的第一个公共结点

思路：我们可以采用简单的双指针法，可以假设A 长度为m， B 长度为n，如果相交，A 和 B相交片段长度为 x， 不相交的片段长度分别为a 和b。

那么如果我们采用双指针法：

当链表 headA 和 headB 都不为空时，创建两个指针 pA和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

  • 每步操作需要同时更新指针 pA 和 pB。

  • 如果指针 pA不为空，则将指针 pA 移到下一个节点；如果指针 pB不为空，则将指针 pB 移到下一个节点。

  • 如果指针 pA为空，则将指针 pA 移到链表 headB的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。

  • 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

那么如果二者相交，则 m = a + x， n = b + x。pA 和 pB 一定在走过 a + b + x 长度时相等。如果二者不相交，则一定不会出现相等（可以分类讨论）。

 /*struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {if(!pHead1 || !pHead2) return nullptr;ListNode* pA = pHead1;ListNode* pB = pHead2;while(pA != pB){if(pA == nullptr) pA = pHead2;else pA = pA->next;if(pB == nullptr) pB = pHead1;else pB = pB->next;}if(pA == nullptr) return nullptr;else return pA;}};

JZ23 链表中环的入口结点

环的题目中，我们知道如何判断是否有环（快慢指针），那么同样的，入口结点也可以用快慢指针解决。只需要：

  • 让快慢指针从链表头出发，快2慢1，如果有环最终必会相遇（这也是判断是否有环的方法）

  • 将快指针回调回链表头，开始快慢都每次各走一步，相遇点即为入口结点。

下面是证明方法：

假设 环如图所示：

 

fast = a + b + n * (b + c); slow = a + b;

同时，fast = 2 slow; --> a = (n - 1)b + n * c;

所以如果让 fast 置为链表头，一次走一步，走 a 长度的，那么 slow 也会走 a 长度，因为 a = (n - 1)b + n * c，因为slow 原本在 a + b 位置， 所以相加，正好得到： a + a + b = (n - 1)b + n * c + a + b = a + n (b + c); 所以恰好会在链表环入口处相遇。

 ​/*struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* fast = pHead;ListNode* slow = pHead;while(fast){slow = slow->next;if(fast->next) fast = fast->next->next;else return nullptr;if(fast == slow){fast = pHead;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;}}return nullptr;}};

JZ22 链表中倒数第k 个结点

我们需要找倒数第k 个节点，那么完全也可以利用双指针法去解，让快指针先走 k步，然后快慢同步走，快指针走到链表尾的时候，由于慢指针和快指针相差k 步，所以慢指针指向的就是第k 个结点。

 /*** struct ListNode {*int val;*struct ListNode *next;*ListNode(int x) : val(x), next(nullptr) {}* };*/class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead ListNode类 * @param k int整型 * @return ListNode类*/ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereif(!pHead || k <= 0) return nullptr;ListNode* pfast = pHead;ListNode* pslow = pHead;for(int i = k; i > 0; --i){if(pfast) pfast = pfast->next;else if(!pfast && i == 0) return pHead;else return nullptr;}while(pfast){pfast = pfast->next, pslow = pslow->next;}return pslow;}};

JZ35 复杂链表的复制

我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为 A→A′→B→B′→C→C′ 。对于任意一个原节点 S，其拷贝节点 S′ 即为其后继节点。

这样，我们可以直接找到每一个拷贝节点 S′ 的随机指针应当指向的节点，即为其原节点 SSS 的随机指针指向的节点 T 的后继节点 T‘ 。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。

当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空，我们需要特别判断这种情况。

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。我们只需要遍历该链表三次。读者们也可以自行尝试在计算拷贝节点的随机指针的同时计算其后继指针，这样只需要遍历两次。 空间复杂度：O(1)。注意返回值不计入空间复杂度。

 /*// Definition for a Node.class Node {public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}};*/​class Solution {public:Node* copyRandomList(Node* head) {if(head == nullptr){return nullptr; //如果为空则不讨论}for(Node* node = head; node != nullptr; node = node->next->next){Node* newNode = new Node(node->val);nodeNew->next = node->next;node->next = nodeNew; //创建新节点在原节点之后}for(Node* node = head; node != nullptr; node = node->next->next){Node* nodeNew = node->next;newNode->random = (node->random != nullptr) ? node->random : nullptr;//修改新链表random的指向}Node* headNew = head->next;for(Node* node = head; node != nullptr; node = node->next){Node* nodeNew = node->next; node->next = node->next->next; //修改原链表的next。nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr; //修改新链表的next指向}return headNew;}};

JZ76 删除链表中重复的结点

注意读题，是排序的链表，所以我们可以使用双指针法，从左往右，如果left 所指的值和 right 所指是否相等，如果相等那么right 右移， 看看新的right 是否也符合相等条件，直至不符合条件，让前面的prev （解答中的node）指向新 right 即可，就是因为我们需要修改前面的指向，所以需要node 变量来记录之前的位置。也恰好是因为prev 不方便，所以我们使用哨兵位头节点来简化。如果不等，那么直接node，left，right都向右移动一个。

 ​/*struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:ListNode* deleteDuplication(ListNode* pHead) {ListNode* newHead = new ListNode(-1);newHead->next = pHead;for(ListNode* node = newHead; node->next && node->next->next;){ListNode* left = node->next;ListNode* right = left->next;if(left->val != right->val){node = node->next, left = left->next, right = right->next;}else{while(right && left->val == right->val) right = right->next;node->next = right;}}return newHead->next;}};


http://chatgpt.dhexx.cn/article/PLe4ucOq.shtml

相关文章

【023】C/C++数据结构之链表及其实战应用

【023】C/C++数据结构之链表及其实战应用

C 链表及其实战应用 引言一、链表的概述二、利用链表设计一个学生管理系统2.1、设计主函数main()2.2、实现插入节点2.3、实现链表的遍历2.4、实现链表的查找2.5、实现删除某个节点2.6、实现释放链表2.7、完整代码 总结 引言 &#x1f4a1; 作者简介&#xff1a;专注于C/C高性能…
阅读更多...
KNN分类算法详解

KNN分类算法详解

参考&#xff1a;https://www.cnblogs.com/listenfwind/p/10311496.html https://www.cnblogs.com/listenfwind/p/10685192.html 1. 概述 KNN 可以说是最简单的分类算法之一&#xff0c;同时&#xff0c;它也是最常用的分类算法之一。注意&#xff1a;KNN 算法是有监督学习中的…
阅读更多...
【python代码实现】朴素贝叶斯分类算法

【python代码实现】朴素贝叶斯分类算法

目录 前置知识1、概念2、算法原理2.1、条件概率2.2、全概率2.3、先验概率2.4、后验概率 朴素贝叶斯分类算法1、构建数据集2、分类概率3、条件概率4、先验概率 前置知识 1、概念 上一篇我们讲到的决策树算法&#xff0c;是反映了一种非常明确、固定的判断选择过程&#xff0c;…
阅读更多...
分类算法-KNN(原理+代码+结果)

分类算法-KNN(原理+代码+结果)

KNN&#xff0c;即K最邻近算法&#xff0c;是数据挖掘分类技术中比较简单的方法之一&#xff0c;简单来说&#xff0c;就是根据“最邻近”这一特征对样本进行分类。 1、K-means和KNN区别 K-means是一种比较经典的聚类算法&#xff0c;本质上是无监督学习&#xff0c;而KNN是分…
阅读更多...
伯努利贝叶斯分类算法

伯努利贝叶斯分类算法

贝叶斯分类的核心概念&#xff1a; 我们对某件事情的判断首先有一个概率&#xff0c;这个概率称为先验概率。先验概率时根据经验总结出来的概率值&#xff0c;如果首先没有经验&#xff0c;那么可以将先验概率设置为50%&#xff0c;随着后面事情的发展&#xff0c;再调整先验概…
阅读更多...
【机器学习原理】KNN分类算法

【机器学习原理】KNN分类算法

上一篇&#xff1a;Logistic回归分类算法 文章目录 一、KNN分类算法&#xff1a;用多数表决进行分类1. 用“同类相吸”的办法解决分类问题可视化下的分类问题 2. KNN分类算法的基本方法&#xff1a;多数表决3. 表决权问题4. KNN的具体含义 KNN分类算法原理1. KNN分类算法的基本…
阅读更多...
Python实现分类算法

Python实现分类算法

前言&#xff1a;出自于学校课程数据挖掘与分析布置的实验小作业&#xff0c;案例经典&#xff0c;代码注释较全&#xff0c;供大家参考。 题目&#xff1a; 现有西瓜挑选数据文件&#xff1a;dataset.txt&#xff0c;编程实现朴素贝叶斯算法&#xff0c;并判断有如下特征的瓜…
阅读更多...
贝叶斯分类算法

贝叶斯分类算法

贝叶斯分类是一类分类算法的总称&#xff0c;这类算法均以贝叶斯定理为基础&#xff0c;故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单&#xff0c;也是常见的一种分类方法。这篇文章我尽可能用直白的话语总结一下我们学习会上讲到的朴素贝叶斯分类算法&#…
阅读更多...
基于Python实现五大常用分类算法(原理+代码)

基于Python实现五大常用分类算法(原理+代码)

读&#xff1a; 在机器学习和统计中&#xff0c;分类算法通过对已知类别训练集的计算和分析&#xff0c;从中发现类别规则并预测新数据的类别。分类被认为是监督学习的一个实例&#xff0c;即学习可以获得正确识别的观察的训练集的情况。 实现分类的算法&#xff0c;特别是在具…
阅读更多...
EIGRP综合实验解析

EIGRP综合实验解析

实验要求 1.R1为ISP,只能配置IP地址 2.R1与R2之间为PPP封装&#xff0c;使用CHAP认证&#xff0c;R1为主认证方 3.R2-R8地址为172.16.0.0/16 4.R4的S1/1口带宽为800K。R4到R2环回为非等开销负载均衡 5.保证更新安全&#xff0c;减少路由条目数量 6.R6到达R8环回通过R7进行 7.R2…
阅读更多...
EIGRP协议

EIGRP协议

EIGRP是距离矢量路由协议&#xff0c;但又非距离矢量那样路由完全是别人告诉&#xff0c;而是通过维护3张表自己对比计算后放入路由表。同样会受水平分割影响。 EIGRP建邻居过程 第一步&#xff1a;路由器R1和R2接口配置EIGRP后&#xff0c;在相应接口上向外组播发送Hello包…
阅读更多...
EIGRP总结

EIGRP总结

EIGRP 增强内部网关路由协议 无类别距离矢量IGP协议&#xff1b; 增量更新—仅触发更新&#xff0c;无周期更新----更新量小&#xff08;DV&#xff09;&#xff0c;可靠性高&#xff08;RTP&#xff09;&#xff0c;保活机制&#xff08;hello&#xff09; 复合度量—多个参数…
阅读更多...
EIGRP

EIGRP

EIGRP增强型网关路由协议 基本内容&#xff1a; Cisco私有&#xff1b;无类别距离矢量协议&#xff1b;跨层封装协议&#xff0c;封装于网络层–协议号88&#xff1b;组播更新&#xff1a;224.0.0.10 &#xff1b;支持非等开销负载均衡&#xff1b;增量更新&#xff08;部分更…
阅读更多...
思科EIGRP配置及基本讲解

思科EIGRP配置及基本讲解

思科EIGRP配置及基本讲解 什么是EIGRP EIGRP全称 [增强型内部网关路由选择协议] 是思科自主研发的动态路由选择协议&#xff0c;按类型划分是一款IGP协议&#xff0c;距离矢量协议&#xff0c;是一款基于传闻的协议。 EIGRP是思科的私有协议&#xff0c;直到13年&#xff0c;此…
阅读更多...
EIGRP协议的配置

EIGRP协议的配置

EIGRP(Enhanced Interior Gateway Routing Protocol&#xff0c;增强型内部网关路由协议)是Cisco公司开发的一个平衡混合型路由协议&#xff0c;它融合了距离向量和链路状态两种路由协议的优点&#xff0c;支持IP&#xff0c;IPX和ApplleTalk等多种网络层协议。由于TCP/IP是当今…
阅读更多...
网络篇 EIGRP协议-27

网络篇 EIGRP协议-27

目录 一、EIGRP的基本概述 二、EIGRP的特点 三、EIGRP的四种重要技术 四、EIGRP的相关术语 五、EIGRP的三张表 1.路由表 2.邻居表 3.拓扑表 六、EIGRP的五个分组 1.Hello分组&#xff1a; 2.Update更新分组&#xff1a; 3.Query查询分组&#xff1a; 4.Reply应答分…
阅读更多...
EIGRP（Enhanced Interior Gateway Routing Protocol，增加型内部网关路由协议）

EIGRP（Enhanced Interior Gateway Routing Protocol，增加型内部网关路由协议）

EIGRP是Cisco公司于1992年开发的一个无类别距离矢量路由协议&#xff0c;它融合了距离矢量和链路状态两种路由协议的优点。EIGRP是Cisco的专有路由协议&#xff0c; 是Cisco的IGRP协议的增加版。IGRP是一种有类距离矢量协议&#xff0c;Cisco IOS 12.3版以后不再支持该协议。 E…
阅读更多...
EIGRP理论详解及基础实验

EIGRP理论详解及基础实验

EIGRP:( Enhanced Interior Gateway Routing Protocol )增强型内部网关路由协议 EIGRP 是一种Cisco专用协议,同时具备链路状态和距离矢量路由协议的优点.只发送变化后的信息(这类似于链路状态协议),同时只将这些信息发送给邻接路由器(这类似于距离矢量协议). 距离矢量路由协议…
阅读更多...
CSMA协议

CSMA协议

介质访问控制 CSMA协议 1-坚持CSMA 非坚持CSMA p-坚持CSMA 三种CSMA对比总结
阅读更多...
3.4.2 CSMA/CD协议

3.4.2 CSMA/CD协议

为了解决各站点争用总线的问题&#xff0c;共享总线使用了一种专用协议CSMA/CD&#xff0c;它是载波监听多址接入/碰撞检测&#xff08;Carrier Sence Multiple Access Collision Detection&#xff09;的英文缩写。 假设站点C要发送帧&#xff0c;它首先进行载波监听&#xff…
阅读更多...
推荐文章

Copyright @ 2022~2023