链表经典题解：剑指 Offer 中的返回倒数第k个节点与合并排序链表

在这个资源中，主要讨论了链表相关的一些经典LeetCode题目，包括《剑指 Offer》中的两道题目：返回倒数第k个节点和合并两个有序链表。以下是每个知识点的详细解析： 1. **返回倒数第k个节点（剑指 Offer 22）**: - **方法一：遍历两次** - 首先遍历一次链表计算链表长度，然后从头开始再次遍历，当遍历次数达到链长减去k时，找到的就是倒数第k个节点。这种方法的时间复杂度为O(N)，空间复杂度为O(1)。 - **方法二：队列实现** - 使用一个大小为k的队列，每次将当前节点入队，当头指针到达null时，队列尾部的节点即为倒数第k个节点。这种方法的时间复杂度也为O(N)，但空间复杂度增加到O(k)。 - **方法三：固定间距指针** - 定义两个指针l和r，l先走k步，然后同时移动，当l到达终点时，r的位置就是倒数第k个节点。这种方法的空间复杂度是O(1)。 2. **合并两个有序链表（LeetCode 21）**: - **最优解：双指针法** - 使用两个指针分别遍历两个链表，将较小的节点依次添加到新链表中，直到其中一个链表遍历完，然后将另一个链表剩余部分接到新链表末尾。时间复杂度为O(m+n)，空间复杂度为O(1)。 3. **其他链表操作：** - **环形链表（LeetCode 141）** - 快慢指针法是最优解决方案，通过控制两个指针的速度差异，可以在O(n)时间内判断是否存在环，空间复杂度为O(1)。 - **相交链表（LeetCode 160）** - 一种方法是让A链表的尾部与B链表的头部相遇，时间复杂度为O(n+m)，另一种方法是比较两个链表节点，直到找到相同的节点，时间复杂度为O(max(n,m))。 这些题目展示了链表数据结构的基本操作以及解决这类问题的不同策略，涉及到了链表的遍历、队列操作、指针技巧以及比较和排序等算法。理解和掌握这些方法对于提高链表相关的编程技能非常有帮助。