企业官网建设流程全解析

前言

• 本文章使用 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 的长度为 x，headB 的长度为 y，两个链表相交部分的长度为 z，如果直接分别从两个链表的头节点开始遍历，则会在遍历时因 x - z 和 y - z 的差依次遍历到相交节点(当x - z != y - z时)，而不是同时遍历到相交位置。所以，先让长链表走差距步，弥补长度差后就能同时遍历判断了。使用假设法先指定 headA 为长链表，headB 为短链表，如果 headA 长度小于 headB，就交换。在所有准备工作完成后，让长链表走差距步
• ➤3.遍历两个链表判断相交节点
  
  接下来就十分纯粹了，由于差距被弥补，长链表距离相交节点与短链表相同，只需遍历判断即可，当 longer 等于 shorter 时，返回两者之一

至此已完成，但此解法的代码有些冗长，需先遍历计数，让长链表走步差后，再同时遍历判断，那能否让代码更优雅呢？
答：能，此题的关键点只在于两个链表的距离差

数学步长归同法

解释：设 headA 的长度为 x，headB 的长度为 y，两个链表相交部分的长度为 z，则满足 x - z + y 等于 y - z + x。知道了这个公式后，可以直接遍历两个链表，当 curA 完成 headA 的遍历指向 NULL 时直接让其从 headB 的头节点继续遍历，curB 同理。这样做的效果会导致遍历距离相同(x + y 等于 y + x)，所以能遍历到同样步长，去除距离差造成的影响，因此只需在遍历时判断相交节点，就能找出两个链表相交的位置。
注：当两个链表不相交时，由于 curA 会依次遍历 headA 和 headB，curB 会依次遍历 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 的 next，cur 从头节点开始遍历，copy 从哨兵节点开始遍历，因此距离差一，改变 copy 节点的 next 指向不会使链表断链，而 cur 的 next 指向一定修改为 cur->next->next，中间的 next 为拷贝节点，每个拷贝节点的 next 又指向原链表节点。每个拷贝节点分离后尾插进 cphead 链表，当循环结束后，返回对应原链表头节点的拷贝节点，而不是返回哨兵节点

⚛️EL PSY CONGROO，十分感谢你的阅读

本期不确定：
要为回文链表判断题添加递归解法吗