【数据结构算法篇】链表面试必刷题4—链表中倒数第k个结点

旧城等待， 2023-09-27 11:53 92阅读 0赞

> 专栏：[《数据结构必刷题》][Link 1]  
> 题目来自：[牛客网][Link 2]和[力扣][Link 3]

题目：链表中倒数第k个结点

题目链接：[点击即可跳转][Link 4]

题目描述：

> 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。  
> 如果该链表长度小于k，请返回一个长度为 0 的链表。

> 数据范围：0 <= n <= 10^5 , 0 <= ai <= 10^9, 0 <= k <= 10^9  
> 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)  
> 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如输入\{1,2,3,4,5\},2时，对应的链表结构如下图所示：  
![在这里插入图片描述][1c36eeae0ce8402eb829c857775bf3b9.png]

> 其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1：

> 输入：\{1,2,3,4,5\},2  
> 返回值：\{4,5\}  
> 说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较

示例2:

> 输入： \{2\},8  
> 返回值：\{\}

解题思路：  
对于这道题，我们可以遍历链表，然后记录链表的长度，再输出倒数第K个结点。这虽然可以解决问题，但是时间复杂度高了，因为遍历了两遍链表。  
如果要遍历一遍链表来解决问题，那么这道题可以使用 快慢指针 \\color\{\#FF0000\}\{快慢指针\} 快慢指针来解决。

> **快慢指针 所谓快慢指针中的快慢指的是指针向前移动的步长，每次移动的步长较大即为快，步长较小即为慢**，常用的快慢指针一般是在单链表中让快指针每次向前移动2，慢指针则每次向前移动1。

我们先定义快慢指针，快指针为 f a s t \\color\{\#FF0000\}\{fast\} fast ,慢指针为 s l o w \\color\{\#0000FF\}\{slow\} slow。  
![在这里插入图片描述][f6cbfd7bd3fa4186a64af62b31e309d0.png]  
既然我们要得到倒数第K个结点，因此我们可以**先让快指针走K步**。当快指针走完后，它们在以相同的速度出发。看下图：  
![在这里插入图片描述][15cc030bafb34d48b762a38a21124fe4.png]  
我们由上图可知，当 f a s t = = n u l l \\color\{\#FF0000\}\{fast==null\} fast==null，此时 s l o w \\color\{\#0000FF\}\{slow\} slow开始之后的结点都是我们要的结点 ，我们只需要返回 s l o w \\color\{\#0000FF\}\{slow\} slow结点就可以了。  
做题要要严谨，我们还要考虑到 空链表、 K 的值不是正数、当 K 过大， f a s t 为空 \\color\{\#FF0000\}\{空链表、K的值不是正数、当K过大，fast为空\} 空链表、K的值不是正数、当K过大，fast为空 这几种情况。接下来就可以写代码了。

public ListNode FindKthToTail (ListNode pHead, int k) {
        
            // write code here
            if(pHead == null || k <= 0){
        //空链表和K的值不是正数这种情况
                return null;
            }
            ListNode slow = pHead;
            ListNode fast = pHead;
            for(int i = 0;i < k;i++){
        
                if(fast == null){
        //判断K的值是否过大，导致fast是否为空
                    return null;
                }
                fast = fast.next;
            }
            //快慢指针同时出发
            while(fast != null){
        
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }

![在这里插入图片描述][5d87fa3695e844cc8149c7f3d6768fe9.png]

[Link 1]: https://blog.csdn.net/m0_63463510/category_12021169.html?spm=1001.2014.3001.5482
[Link 2]: https://www.nowcoder.com/exam/oj?tab=%E8%AF%AD%E6%B3%95%E7%AF%87&topicId=290
[Link 3]: https://leetcode.cn/
[Link 4]: https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tqId=1377477&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=/exam/oj?page=1&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=295
[1c36eeae0ce8402eb829c857775bf3b9.png]: https://img-blog.csdnimg.cn/1c36eeae0ce8402eb829c857775bf3b9.png
[f6cbfd7bd3fa4186a64af62b31e309d0.png]: https://img-blog.csdnimg.cn/f6cbfd7bd3fa4186a64af62b31e309d0.png
[15cc030bafb34d48b762a38a21124fe4.png]: https://img-blog.csdnimg.cn/15cc030bafb34d48b762a38a21124fe4.png
[5d87fa3695e844cc8149c7f3d6768fe9.png]: https://img-blog.csdnimg.cn/5d87fa3695e844cc8149c7f3d6768fe9.png