输入一个链表，输出该链表的倒数第 k 的结点

左手的ㄟ右手 2023-10-13 11:38 20阅读 0赞

**一、思路**  
  
假设 K 是 2，根据下面的图片可以看出，倒数第 K 个结点就是 45。

![ef6718f65e154a95b56cef897a28e866.png_pic_center][]

需要注意的前提是，K 不能是负数也不能是 0 并且也不能超过链表的结点个数，因为要保证 K 是在链表的范围里，才能找到 K，然后返回这个结点，如果这个结点就不可能找的到，就不可能返回它。  
  
将所有的结点都遍历一遍后才有可能找到倒数第 K 个结点，因此肯定是要使用循环来一个结点一个结点遍历。  
接着就是判断当前的结点是不是目标结点，如果是那就跳出循环，返回这个结点；如果不是，那就继续找下一个结点，直到将链表完整的遍历一边。

接下来要实现的就是循环的结束条件，也就是如何判断当前的结点是不是 目标结点。  
可以先定义 fast 和 slow 两个指针，在最开始的时候都指向头结点的位置，但是要先让 fast 走K-1步。

具体会指向哪个结点要根据 K 来决定，如果此时 K 是负数或者是 0，再或者超过了链表的结点个数，  
此时 fast 指向的位置肯定是不合法的。

![6e8da3f8b66540cbb032a79f0c414ad7.png_pic_center][]  
当 K 为 0，fast 就会走到 0-1 的位置上，此时明显不合法。

![da9aae20a79a4fc7a709cf8eb60fa0ce.png_pic_center][]  
当 K 为 -1时，fast 就会走到 -1-1 的位置上，此时依然明显不合法。

![1561d3390313469c98e5bc01daddd95a.png_pic_center][]  
当 K 的值超过了链表结点个数的时候，fast 最终会走到超过链表的位置。

以上三种不合法的情况，显然是不能够为我所用的。  
  
因此在代码最开始时，肯定是要先判定当前的 K 是不是合法的，如果合法再进入到下一步；  
如果不合法，就直接返回一个 null，以此来表示当前 K 的给值是有问题的。

当 fast 走完 K-1 步后，再让两个结点一步一步的走，由于 fast 是先走的，因此肯定会比 slow 走得多。当 fast 的下一个结点为空时，此时 slow 指向的就正好是倒数第 K 个结点了。此时的循环就结束了，跳出以后直接返回 slow 即可。

![7b6148e9ecc644c3bbe483ae8f1f2618.png_pic_center][]  
当 K 的值为 1 时，fast 走 K-1 步也就是一步也不动，两个指针是在头结点的位置就开始一起移动的。  
当 fast 的下一个结点为空时，可以看到 slow 指向的就恰好是倒数第 1(K的值) 个结点 。  
  
这种思路不受奇数结点与偶数结点的影响，不管是链表结点是奇数还是偶数，这种方法都适用。

![4e8b3baf76074e899588e3628b5053f4.png_pic_center][]  
当 fast 走完 K-1步后会始终比 slow 多走一步，因此当 fast 的下一个结点为空时 slow 指向的恰好是 fast 的前一个结点，也就是倒数第 2 (K的值)个结点。

**二、详细过程**  
  
1、首先要判断 K 的取值是不是合法的，如果不是合法的就直接返回一个 null。

//k位置不合法
    if (k <= 0 || this.head == null) {
        
        return null;
    }

2、定义两个指针，一个叫做 **fast**，一个叫做 **slow**，然后让它们都指向头结点。

//定义一个fast和slow指向head
    ListNode fast = this.head;
    ListNode slow = this.head;

3、先让 fast 走 K -1 步。

while (k - 1 != 0) {
        
        fast = fast.next;
        if (fast == null) {
        
            return null;
        }
        k--;
    }

假设此时的 K 取值是 2，fast 会先走 1 步，如果当前的 K 的取值是 1 ，fast 一步也不会走。  
上述的循环会直接进不去。  
  
![d10b92e2b84c433ab04be56d982c812e.png_pic_center][]  
当 K 取值是 2 是，fast 会先走到第二个结点的位置。

4、让两个指针同时移动。

//然后两个一起走
    //当fast.next==null的时候，slow所指的位置就是倒数第k个结点
    while (fast.next != null) {
        
        //两个一起走
        fast = fast.next;
        slow = slow.next;
    }
    return slow;//此时slow指向的就是倒数第k个结点

![29a3d33f812c4fc3b485a733ceaa8acb.png_pic_center][]  
倒数第2个结点就是此时 slow 指向的这个结点。  
  
完整代码

public ListNode findKthToTail(int k) {
        
        //k位置不合法
        if (k <= 0 || this.head == null) {
        
            return null;
        }
    
        //定义一个fast和slow指向head
        ListNode fast = this.head;
        ListNode slow = this.head;
    
        //先让fast走k-1步
        while (k - 1 != 0) {
        
            fast = fast.next;
            if (fast == null) {
        
                return null;
            }
            k--;
        }
    
        //然后两个一起走
        //当fast.next==null的时候，slow所指的位置就是倒数第k个结点
        while (fast.next != null) {
        
            //两个一起走
            fast = fast.next;
            slow = slow.next;
        }
        return slow;//此时slow指向的就是倒数第k个结点
    }

![99220d9b84c44164bb2ce93db97954c6.png][]  
  
可以看到此时通过了牛客上的测试。  
\\

[ef6718f65e154a95b56cef897a28e866.png_pic_center]: https://img-blog.csdnimg.cn/ef6718f65e154a95b56cef897a28e866.png#pic_center
[6e8da3f8b66540cbb032a79f0c414ad7.png_pic_center]: https://img-blog.csdnimg.cn/6e8da3f8b66540cbb032a79f0c414ad7.png#pic_center
[da9aae20a79a4fc7a709cf8eb60fa0ce.png_pic_center]: https://img-blog.csdnimg.cn/da9aae20a79a4fc7a709cf8eb60fa0ce.png#pic_center
[1561d3390313469c98e5bc01daddd95a.png_pic_center]: https://img-blog.csdnimg.cn/1561d3390313469c98e5bc01daddd95a.png#pic_center
[7b6148e9ecc644c3bbe483ae8f1f2618.png_pic_center]: https://img-blog.csdnimg.cn/7b6148e9ecc644c3bbe483ae8f1f2618.png#pic_center
[4e8b3baf76074e899588e3628b5053f4.png_pic_center]: https://img-blog.csdnimg.cn/4e8b3baf76074e899588e3628b5053f4.png#pic_center
[d10b92e2b84c433ab04be56d982c812e.png_pic_center]: https://img-blog.csdnimg.cn/d10b92e2b84c433ab04be56d982c812e.png#pic_center
[29a3d33f812c4fc3b485a733ceaa8acb.png_pic_center]: https://img-blog.csdnimg.cn/29a3d33f812c4fc3b485a733ceaa8acb.png#pic_center
[99220d9b84c44164bb2ce93db97954c6.png]: https://img-blog.csdnimg.cn/99220d9b84c44164bb2ce93db97954c6.png