【数据结构和算法】链表的综合算法练习：1.返回倒数第k个节点 2.相交链表 3.回文链表

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人等方向学习者
❄️个人专栏：《C语言》《【初阶】数据结构与算法》
✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 一、返回倒数第k个节点
  • 1.1题目
  • 1.2 算法原理
  • 1.3 代码
• 二、相交链表
  • 2.1 题目
  • 2.2 算法原理
  • 2.3 代码
• 三、回文链表
  • 3.1 题目
  • 3.2 算法原理
  • 3.3 代码
• 总结与每日励志

前言

链表作为数据结构的基础核心，是算法面试与嵌入式开发中高频考察的重点。本文聚焦三道经典链表真题，通过快慢指针、链表反转等核心技巧，拆解倒数第 k 个节点、回文链表与相交链表的解题逻辑，结合代码实现与避坑指南，助力高效掌握链表解题思维。

一、返回倒数第k个节点

1.1题目

链接：返回倒数第k个节点

1.2 算法原理

核心思想: 类快慢指针，定义两个指针slow和fast让fast先走k步使得fast与slow始终相差k当fast走到NULL时slow便是指向链表的倒数第k个节点

1.3 代码

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;*};*/ typedef struct ListNode* ListNode; int kthToLast(struct ListNode* head, int k){ ListNode slow = head; ListNode fast = head;while(k--) fast = fast->next;while(fast){ fast = fast->next; slow = slow->next;}return slow->val;}

二、相交链表

2.1 题目

链接：相交链表

注： 这道题是以进阶的要求来做的

2.2 算法原理

核心思想： 寻找中间节点 + 反转链表
寻找中间节点然后反转中间节点以及中间节点后的链表节点，此时链表的尾节点成为新的中间节点，用头节点开始与中间节点开始比较，遍历两部分链表即可

如何寻找中间节点
核心思想：快慢指针（2*slow == fast）

注意：不能fast->next && fast当遇到偶数链表会造成对空指针解应用

如何反转链表？

2.3 代码

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;*};*/ typedef struct ListNode* ListNode;//寻找中间节点 ListNode seek_mid(ListNode head){ ListNode slow = head; ListNode fast = head;//慢指针走一步，快指针走两步 while(fast && fast->next){ slow = slow->next; fast = fast->next->next;}return slow;}//逆置 ListNode reserve_mid(ListNode head){ ListNode n1 =NULL; ListNode n2 = head; ListNode n3 = head->next;while(n2){ n2->next = n1; n1 = n2; n2 = n3;if(n3) n3 = n3->next;}return n1;} bool isPalindrome(struct ListNode* head){//寻找中间节点 ListNode mid =seek_mid(head);//逆置 ListNode rmid =reserve_mid(mid); ListNode cur = head;while(cur && rmid){if(cur->val != rmid -> val)returnfalse; cur = cur->next; rmid = rmid->next;}returntrue;}

三、回文链表

3.1 题目

链接：回文链表

3.2 算法原理

题目的核心问题： 链表是否相交？ + 相交如何找到相交节点？
（1） 如何链表是否相交？— 链表相交尾节点必定相同
（2） 如何找到相交节点？ — 在两个链表寻找尾节点时统计两个链表的长度，判断做差，让长的链表先走相差的步数，使得两个链表长度一致，然后遍历两个链表判断相交节点即可。

注： 在判断时不管是尾部节点还是相交节点都应该是判断地址而不是数值，因为节点存储的值可能一致从而导致判断错误。

3.3 代码

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;*};*/ typedef struct ListNode* ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){ ListNode cur1 = headA; ListNode cur2 = headB; int lena =1,lenb =1;//判断尾节点是否相同 while(cur1->next){ lena++; cur1 = cur1->next;}while(cur2->next){ lenb++; cur2 = cur2->next;}if(cur1 != cur2)returnNULL; int gap =abs(lena - lenb); ListNode shortlist = headA; ListNode longlist = headB;if(lena >lenb){ shortlist = headB; longlist = headA;}//让长的先走追平链表长度 while(gap--) longlist = longlist->next;while(longlist != shortlist){ longlist = longlist->next; shortlist = shortlist->next;}return longlist;}

总结与每日励志

✨ 本文梳理了三类链表问题的最优解法，核心在于灵活运用指针策略简化操作，同时需注重空指针等边界条件的处理。每一次代码调试的突破，都是逻辑思维的进阶。2026 年，愿你在技术之路上步步为营，深耕不辍，用坚持敲开梦想的大门，永远相信美好的事情即将发生！