算法闯关日记 Episode ：解锁链表新副本——破解「相交」迷局与「回文」谜题
🔥@晨非辰Tong： 个人主页
👀专栏：《C语言》、《数据结构与算法入门指南》
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
文章目录
引言
在算法学习中，链表因其灵活的结构成为高频考点。本期将攻克两大经典问题：「相交链表」 与「链表的回文结构」。跟随本篇题解，逐步拆解问题，提升链表类问题的实战能力
一、相交链表
题目链接：160.相交链表-力扣(LeetCode)
- 题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构 。
- 实现示例：
1.1 思路解答 + 作图演示
- 算法思路：
由于是单链表，节点只保存着下一个节点的地址，那么初步可以确定为遍历两个链表，那么该如何对俩个链表进行遍历呢？
- 简单的对两个链表分别进行遍历，寻找相同的
next（相同的节点地址）。（废弃）
经过作图发现，只是简单的分别遍历比较的话，如果两个链表的长度不相同，就会导致在相交的节点两个链表的遍历会错开，直到遍历完都没有找到。那么，何解？？
- 先让较长的链表走完两个链表长度的差值。（最优解）
以较长的链表B为基准，将链表A依次与链表B对比，寻找相同的节点。（可行，备选）
这个方法可行，但是显然易见：需要两个循环的嵌套，时间复杂度O(N^2^)。
那么，为了解决来链表长度不同导致的遍历步调不一致，就让长的链表先走，让两个来年表同起点。经过作图发现，让B链表先走差值（1位），之后二者的遍历步调一致，最终在节点c1相遇。时间复杂度：O(N)。
1.2 验证算法
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){//求出两个链表的长度//创建临时变量，不改变链表结构 ListNode* pa = headA; ListNode* pb = headB;int sizeA =0, sizeB =0;//循环求长度while(pa){ sizeA++; pa = pa->next;}while(pb){ sizeB++; pb = pb->next;}//长度差值，使用绝对值函数int gap =abs(sizeA - sizeB);//判断链表的长短 ListNode* longlist = headA; ListNode* shortlist = headB;if(sizeA < sizeB){ longlist = headB; shortlist = headA;}//长链表先走gap步while(gap--){ longlist = longlist->next;}//同时遍历while(longlist){//节点相同if(longlist == shortlist){return longlist;}//节点不同 longlist = longlist->next; shortlist = shortlist->next;}//没有相同的节点returnNULL;}二、链表的回文结构
题目链接：链表的回文结构_牛客网
- 题目描述:
对于一个链表，请设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
实现示例：
2.1 思路解答 + 作图演示
- 算法思路：
因为有链表长度<=900的前提，那么就可以将链表转换为数组（数组大小已知，空间复杂度不变），创建数组将链表节点的数值全部存放，再比较。
这个思路跟容易就想到了，当然，这是一个取巧的方法，如果题目没有给出关于链表长度的限制，就不能使用这个方法了。
创建新的链表，将原链表的所有节点重新拷贝一份，再将链表进行反转，与原链表比较。
2.2 验证算法
- 验证算法思路2：将链表转换为数组，创建数组将链表节点的数值全部存放，再比较。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPalindromeList{public:boolchkPalindrome(ListNode* A){// write code here//创建数组int arr[900]={0};//遍历链表，将数值存放在数组中 ListNode* pcur = A;int index =0;while(pcur){ arr[index++]= pcur->val; pcur = pcur->next;}//创建左右指针，双方向遍历数组比较int left =0;int right = index -1;while(left < right){if(arr[left]!= arr[right]){returnfalse;} left++; right--;}returntrue;}};/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPalindromeList{public://找到中间节点 ListNode*middleNode(structListNode* head){//创建快慢指针 ListNode* fast,*slow;//首先都指向头节点 fast = head; slow = head;//循环条件将两种情况都包含while(fast !=NULL&& fast->next !=NULL)//条件换顺序？{//慢指针移动一节点 slow = slow->next;//快指针移动两个节点 fast = fast->next->next;}//返回slowreturn slow;}//从中间节点开始反转链表 ListNode*reverseList(structListNode* head){//创建三个指针 ListNode* n1,* n2,* n3;//链表为空if(head ==NULL){return head;}//链表不为空//首先n1指向空 n1 =NULL; n2 = head; n3 = n2->next;while(n2)//循环条件n2不为空（不超出链表）{ n2->next = n1; n1 = n2; n2 = n3;//当n2到达尾节点时，n3为空，不能对空指针解引用if(n3){ n3 = n3->next;}}return n1;}boolchkPalindrome(ListNode* A){//找到中间节点 ListNode* mid =middleNode(A);//从中间节点开始反转 ListNode* right =reverseList(mid);//遍历原链表和反转之后的链表比较值是否相等 ListNode* left = A;while(right){if(right->val != left->val){returnfalse;} right = right->next; left = left->next;}returntrue;}};总结
🍓 我是晨非辰Tong！若这篇技术干货帮你打通了学习中的卡点： 👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长 ❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量 ⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用 💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑 🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解 技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！ 结语：
「相交链表」的关键在于同步遍历：通过计算长度差与双指针同步移动，巧妙化解链表长度不一致的遍历难题，最终实现O(N)时间复杂度的高效判定。
「链表的回文结构」则需多技巧组合：寻找中间节点（快慢指针）与局部反转（三指针法）的结合，既满足了O(1)空间复杂度的要求，又通过对称比较精准判断回文特性。
两题共同体现了链表问题的核心解法——通过指针操作优化遍历路径，将复杂问题拆解为已知子问题，最终用简洁逻辑攻克难关。
