目录前言一、相交链表二、环形链表三、环形链表 ||四、链表分割五、随机链表的复制结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》《笔试算法》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、相交链表160.相交链表*Definitionforsingly-linked list.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*/classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){// 如果有任何一个链表为空直接返回 nullptrif(headAnullptr||headBnullptr)returnnullptr;ListNode*pAheadA;ListNode*pBheadB;// 只要两个指针不相等就继续走// 包含两种相遇情况// 1. 相交于某个节点pA pB 且都不为空// 2. 不相交同时走到各自拼接后的链表末尾pA pB nullptrwhile(pA!pB){// pA 走到底就去走 B否则继续往下走pApAnullptr?headB:pA-next;// pB 走到底就去走 A否则继续往下走pBpBnullptr?headA:pB-next;}returnpA;}};核心思路双指针法假设链表 A 的长度为 a c链表 B 的长度为 b c。其中 c 是它们相交部分的长度如果不相交则 c 0。我们创建两个指针 pA 和 pB分别初始化为链表 A 和链表 B 的头节点 headA 和 headB。两个指针每次分别向后走一步。关键点当 pA 遍历到链表 A 的末尾即变成 nullptr时我们将它重定向到链表 B 的头节点 headB 继续遍历同理当 pB 遍历到链表 B 的末尾时重定向到链表 A 的头节点 headA。这样一来pA 走过的总路程是 a c b而 pB 走过的总路程是 b c a。因为 a c b b c a且两个指针每次同时走一步所以两个指针一定会同时到达相交节点可以画图验证如果两个链表不相交c 0那么 pA 和 pB 会同时走完 a b 的长度最后同时变成 nullptr退出循环刚好返回 null。二、环形链表环形链表/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:boolhasCycle(ListNode*head){// 初始化快慢指针都指向头节点ListNode*slowhead;ListNode*fasthead;// 快指针每次走两步所以需要确保 fast 和 fast-next 都不是空指针while(fast!nullptrfast-next!nullptr){slowslow-next;// 慢指针走一步fastfast-next-next;// 快指针走两步// 如果两个指针相遇说明链表中有环if(slowfast){returntrue;}}// 如果循环结束说明快指针走到了链表尽头没有环returnfalse;}};算法思路快慢指针你可以把这个问题想象成两个人在环形跑道上赛跑我们定义两个指针一个慢指针slow一个快指针fast初始都指向链表的头节点 head。慢指针每次向前移动 1 步快指针每次向前移动 2 步。如果没有环快指针由于跑得快一定会先到达链表的末尾遇到 nullptr此时我们可以断定链表无环返回 false。如果有环快指针和慢指针最终都会进入环中。由于快指针每次比慢指针多走 1 步这就好比快指针在以 1 步/次 的相对速度追赶慢指针。只要在环内快指针最终一定会从背后追上并与慢指针相遇。一旦相遇说明有环返回 true。要点补充这里循环条件为什么为什么不用加上slow nullptrslow 一次只走 1 步fast 一次走 2 步fast 的遍历进度永远领先 slow只要循环能正常进入fast、fast-next 均有效说明链表还有至少 2 个后续节点slow 当前一定是合法节点执行slow slow-next后依然合法。三、环形链表 ||142.环形链表 ||思路解析快慢指针阶段 1判断是否有环快慢指针同时从头出发slow 走 1 步 / 次fast 走 2 步 / 次若fast遇nullptr无环返回nullptr若两指针相遇有环记录相遇点进入阶段 2。阶段 2定位入环起点新指针ptr1从头出发ptr2从相遇点出发两指针同速1 步 / 次 前进根据数学推导再次相遇的节点就是入环第一个节点返回该节点。题目中代码涉及的数学推导/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:ListNode*detectCycle(ListNode*head){ListNode*slowhead;ListNode*fasthead;// 1.判断是否有环while(fast!nullptrfast-next!nullptr){slowslow-next;fastfast-next-next;// 如果快慢指针相遇说明有环if(slowfast){// 2.寻找入环节点ListNode*ptr1head;// 从头节点重新开始一个指针ListNode*ptr2slow;// 另一个指针从相遇点开始// 两个指针每次都走一步再次相遇的点即为入环节点while(ptr1!ptr2){ptr1ptr1-next;ptr2ptr2-next;}returnptr1;}}// 遍历结束都没有相遇说明无环returnnullptr;}};四、链表分割链表分割算法思路双链表双指针我们可以创建两个新的“虚拟头结点”dummy head分别代表两个新的链表lessHead用来存放所有小于 x的节点。greaterHead用来存放所有大于或等于 x的节点。我们只需要遍历原链表一次遇到 x 的节点就把它接到 lessHead 所在的链表后面。遇到 x 的节点就把它接到 greaterHead 所在的链表后面。遍历结束后将 less 链表的尾部连接到 greater 链表的头部就完成了整个分割过程。因为是顺序遍历并追加所以原本的相对顺序得到了完美的保留。/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPartition{public:ListNode*partition(ListNode*pHead,intx){// 如果链表为空或者只有一个节点直接返回if(pHeadnullptr||pHead-nextnullptr){returnpHead;}// 创建两个虚拟头节点简化后续链表拼接的边界判断ListNode*lessDummynewListNode(0);ListNode*greaterDummynewListNode(0);// 准备两个尾指针用于向两个链表中追加节点ListNode*lessTaillessDummy;ListNode*greaterTailgreaterDummy;// 遍历原链表ListNode*currpHead;while(curr!nullptr){if(curr-valx){// 小于 x 的节点追加到 less 链表lessTail-nextcurr;lessTailcurr;}else{// 大于等于 x 的节点追加到 greater 链表greaterTail-nextcurr;greaterTailcurr;}currcurr-next;}// 【极其重要的一步】:// 大于等于 x 的链表尾节点的 next 可能指向原链表中的某个节点// 必须将其置为 nullptr否则可能会在拼接后形成环greaterTail-nextnullptr;// 将两个链表拼接起来小链表的尾连接大链表的头跳过 dummy 节点lessTail-nextgreaterDummy-next;// 最终返回新链表的真实头节点ListNode*newHeadlessDummy-next;// 释放临时分配的虚拟头节点良好的编程习惯防止内存泄漏deletelessDummy;deletegreaterDummy;returnnewHead;}};要点讲解1. 忘记断开尾部造成环这是面试中最常见的错误。greaterTail-next nullptr;这一句千万不能漏掉。原链表最后一个放到 greater 链表中的节点它的 next 可能还指向着原链表中一个较小的节点。如果不把它置空拼接后链表中就会出现死循环。例如原链表 5 - 2 - 3 - nullptr分割值 x 4处理第一个节点 55 4所以追加到 greater 链表。greaterTail 移动到节点 5。关键点 此时节点 5 被挂到了 greater 链表上但它的 next 指针依然指向原链表中的下一个节点 2在遍历结束后两个链表在内存中的真实状态less 链表dummyLess - 2 - 3 - nullptr因为3原来就在末尾它的next本来就是nullgreater 链表dummyGreater - 5。节点 5 的 next 我们从未主动修改过它仍然保留着最初的状态也就是指向节点 2我们直接执行两链表拼接的代码lessTail-next greaterDummy-next;也就是让 节点 3 指向 节点 5结果 产生了一个 2 - 3 - 5 - 2 - 3 - 5 … 的无限死循环。当你尝试打印或者遍历返回的新链表时程序就会因为内存溢出或超时而崩溃。五、随机链表的复制Leetcode 138. 随机链表的复制该题目在STL的文章部分已经写过我这里就不重复写了map 与 unordered_map 结构实战指南从随机链表复制到单词识别再探稳定与非稳定排序结语