博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub算法专栏路漫漫其修远兮吾将上下而求索文章目录前言一、反转链表题目解读双指针法递归法二、链表的中间节点题目解读长度计数法快慢指针法三、回文链表题目解读数组判断法折半判断法四、相交链表题目解读距离弥补法数学步长归同法五、随机链表的复制题目解读原地复制拆分法前言本文章使用 c 语言进行题目讲解需读者彻底掌握单链表的概念和原理适合刚手撕完单链表实现后想实际应用的读者一、反转链表先看题目题目解读有一个单向不循环链表要求将每一个节点的 next 指针都从指向后一个节点修改为指向前一个结点实现链表方向的整体逆置。特殊节点有头节点和尾节点当链表反转后原头节点变为尾节点由于头结点无前驱因此将 next 指向 NULL。原尾节点的 next 指向 NULL反转后尾节点变为反转链表的头节点双指针法解释由于链表不能随机访问或反向遍历所以我们一定需从头节点开始遍历逐步修改每个结点的指针指向同时用一个指针遍历另一个指针记录当前节点的前驱。定义指向头结点的前驱结点的指针 prev指向当前节点的指针 cur利用 cur 遍历整个链表当 cur 为空时完成整个链表的反转。因为要修改 cur 的 next 指向为防止断链先使用 next 临时存储后继节点后将 cur-next 指向前驱节点。更新前驱节点为当前节点移动当前节点到后继节点如此循环往复当 cur 为空时prev 为原尾节点是反转链表的头节点因此直接返回递归法解释递到链表的最后一个节点head NULL 主要用于判断传入链表为空的情况否则一定能通过 head-next 找到尾节点后返回因为链表反转后的头结点一定是原尾节点因此判定递归函数的返回值每次都是原尾节点。提问应该如何修改每个节点的指针指向反转链表?第一步使用当前节点 head 修改 head 的后继节点的 next 指向 head相当于通过每个待反转节点的前驱修改其本身的 next 指向前驱节点每个节点的 next 都是被前驱节点修改的。第二步让 head 的 next 指向 NULL。当 head 等于原头节点时层数是递归的最后一层如果不执行此操作就会导致原头节点的 next 仍指向后继节点而不是指向 NULL造成原头节点的 next 指针和后继节点的 next 指针相互指向链表成环。至于其余情况可以理解为对下一轮要修改指针的初始化二、链表的中间节点先看题目题目解读有一个链表要找到该链表的中间节点如果链表的总节点个数为偶数返回中间两个中的后一个长度计数法解释首先遍历链表统计总长利用总长遍历总长的一半找到中点注意从 head 开始遍历相当于已经遍历过一个节点了。完整的判定为 len / 2 1为奇数时向下取整后加一为中点为偶数时加一刚好是中间的第二个节点但这是在起始位置不为 head 的情况因此最后都走 len / 2 步快慢指针法解释定义一个快指针和一个慢指针从头结点开始遍历链表快指针每次走两步慢指针每次走一步当快指针走到链表末尾时慢指针必然为中间节点。当链表总长度为奇数时快指针和慢指针一定走偶数步因为从头节点开始奇数 - 1等于偶数因此最后快指针必然在链表的尾节点因为 fast-next 终止。当链表总长度为偶数时快指针走偶数步但走到链表的尾节点的后继节点 NULL终止因为偶数 - 1等于奇数但快指针只能一次走两步因此在尾节点后终止。慢指针走奇数步到两个中间节点的后一个停止。在遍历链表时为防止链表总长度为偶数的情况需先判断 fast 不为空注如果题目要求在链表长度为偶数时返回中间的第一个节点只需将 while 循环的遍历条件修改为 fast-next fast-next-next 即可fast-next 依旧是判断奇数的条件而 fast-next-next 就相当于在偶数长度时让快指针“少走一步”走到尾节点的前一个结点时终止三、回文链表先看题目题目解读回文指链表从左到右和从右到左遍历直到中间节点的结果相同如果相同返回 true不同返回 false。换句话说就是判断链表中的值是否对称数组判断法解释由于题目给定链表的节点数量范围能直接定义一个数组将每个节点中的值存储到数组中判断使用 left 指向头right 指向尾每次分别往前和后移动一步如果 left 和 right 的值不相等代表链表不是回文链表判断直到 left 大于等于 right 为止返回 true折半判断法解释在链表的中间折半反转折半链表的后半段依次从前半段和后半段的表头开始遍历判断如果两个链表全等返回 true否则返回 false。注意折半链表并反转后前半段链表的末尾仍连接着后半段链表的尾节点因此在链表长度为奇数时两个从表头开始遍历的指针一定会在原链表的中间节点相遇因此判断时一定相等无需担心因长度不同导致的不匹配问题。循环的结束条件为当有一个遍历指针指向 NULL 时终止代表已完成前半段对比后半段链表的判断在代码中主要使用后半段链表指针确定因为前半段尾节点的 next 仍连着后半段的尾节点在原链表长度为偶数时后半段链表遍历指针先走到 NULL四、相交链表先看题目题目解读先说链表的相交链表中的每一个节点都有唯一后继当两个链表相交时肯定不能再从相交节点分叉使整体呈 X 字形所以从相交节点开始两个链表合并为一个整体呈 Y 字形。如果不相交那这两个链表就是互相独立的整体呈两条直线或点。题目保证给定链表不为循环链表要求如果链表相交就找到相交的节点(题目图示中为c1)不相交返回 NULL注意我们编写的题解代码不能修改两个链表题目要求保持原始结构距离弥补法这段题解虽然看起来很长但总结起来就只有三个步骤➤1.遍历两个链表统计长度和判断是否相交上面我们探讨过两个相交链表分别遍历到尾节点后其指向一定为同一个节点。如果不为同一个节点则代表链表不相交直接返回 NULL。在遍历的同时统计链表长度因为遍历到尾节点则计数从零开始会与原链表长度差一但并不影响此题的解我们只用这两个长度变量计算长度差至于为何请继续阅读注题目给定两个链表的长度至少为1因此遍历找尾的两个循环条件不会出现空指针解引用问题➤2.用假设法先让长链表走差距步先说结论此题的关键在于两个相交链表的长度差设 headA 的长度为 xheadB 的长度为 y两个链表相交部分的长度为 z如果直接分别从两个链表的头节点开始遍历则会在遍历时因 x - z 和 y - z 的差依次遍历到相交节点(当x - z ! y - z时)而不是同时遍历到相交位置。所以先让长链表走差距步弥补长度差后就能同时遍历判断了。使用假设法先指定 headA 为长链表headB 为短链表如果 headA 长度小于 headB就交换。在所有准备工作完成后让长链表走差距步➤3.遍历两个链表判断相交节点接下来就十分纯粹了由于差距被弥补长链表距离相交节点与短链表相同只需遍历判断即可当 longer 等于 shorter 时返回两者之一至此已完成但此解法的代码有些冗长需先遍历计数让长链表走步差后再同时遍历判断那能否让代码更优雅呢答能此题的关键点只在于两个链表的距离差数学步长归同法解释设 headA 的长度为 xheadB 的长度为 y两个链表相交部分的长度为 z则满足 x - z y 等于 y - z x。知道了这个公式后可以直接遍历两个链表当 curA 完成 headA 的遍历指向 NULL 时直接让其从 headB 的头节点继续遍历curB 同理。这样做的效果会导致遍历距离相同(x y 等于 y x)所以能遍历到同样步长去除距离差造成的影响因此只需在遍历时判断相交节点就能找出两个链表相交的位置。注当两个链表不相交时由于 curA 会依次遍历 headA 和 headBcurB 会依次遍历 headB 和 headA步长依旧相同因此最后 curA 会遍历到 headB 的 NULL与此同时 curB 也会遍历到 headA 的 NULL不满足循环条件 curA ! curB 后终止(NULL NULL)最后返回两者其一即可五、随机链表的复制先看题目题目解读有一个每个节点都增加了 random 指针的单链表random 指针可能指向链表中的任何一个节点包括该节点自身和 NULL。要求完全拷贝一份相同的单链表且这份拷贝的单链表不能与原链表有任何衔接原地复制拆分法➤循环一遍历原链表分别在原链表每个节点后插入一个新节点每个新结点的 val 和 next 复制原链表的对应节点中的值且将新节点的 random 初始化为 NULL便于循环二操作。循环一拷贝 val 与 next 并预处理 random。➤循环二利用原链表处理拷贝节点的 random 指针由于当前拷贝链表中每个结点的相对位置与原链表相同这意味着如果 random 的指向非空就能通过原链表中每个节点的 random 的 next 找到拷贝链表中对应的节点因为每个拷贝节点正链接在每个原链表节点后。当原链表节点的 random 指向空时无需操作因为循环一已完成每个拷贝节点的 random 的预处理否则还需判断 random 指向空的情况并将对应拷贝节点的 random 也指向空➤循环三将拷贝链表与原链表分离并还原原链表定义一个哨兵节点用于链接分离后的拷贝链表同时从该节点开始链接当前 cur 的 nextcur 从头节点开始遍历copy 从哨兵节点开始遍历因此距离差一改变 copy 节点的 next 指向不会使链表断链而 cur 的 next 指向一定修改为 cur-next-next中间的 next 为拷贝节点每个拷贝节点的 next 又指向原链表节点。每个拷贝节点分离后尾插进 cphead 链表当循环结束后返回对应原链表头节点的拷贝节点而不是返回哨兵节点⚛️EL PSY CONGROO十分感谢你的阅读本期不确定要为回文链表判断题添加递归解法吗