【Java实现】链表中倒数第k个结点

🎈目录🎈

问题描述🔒

输入输出实例：

解题分析🔑

代码实现🔓

---

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

问题描述

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

输入输出实例：

解题分析

         对于这道题，最简单的做法就是先遍历一遍链表，得到链表的长度然后在找倒数第k个结点。

        但是这种解法太过常见，在面试时，面试官可能会让我们只遍历一次就找到相应的结点。

这时我们就要运用快慢指针的思想来解这道题。

我们来做这道题之前，可以先看一下这道题的简单版：链表的中间结点

所谓快慢指针，就是设置两个指针，一个指针走的快，另一个指针走的慢，或者一个指针先走，一个指针后走。

对于这道题，我们看下图。

 当 slow 指向倒数第三个结点，fast 指向尾结点，那么 slow  到 fast 需要几步？答案是2步。

所以当k合法的情况下，我们可以先让快指针走k-1步，然后然后两个指针一块走。

例如一个链表长度为5，我们要找倒数第三个结点。

我们可以先让 fast 走 k-1（2） 步，然后让 fast 和 slow 一块走，当 fast.next == null 时，那么 slow 所指向的就是倒数第 k（3）个结点。

 综上，我们的代码逻辑就可以写为

        ListNode slow = head;
        ListNode fast = head;
        int i = k-1;
        while(i > 0){
            i--;
            fast = fast.next;
        }
 
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }

这是在 k 合法的情况下，当 k 不合法时，我们该如何判断呢？

如下图，当链表长度为5，要找倒数第6个结点，那 fast 就要先走 5 步。5 步走完时，fast 就为null。所以我们要在 fast 向前（k-1）时就要判断 fast 是否为空，如何为空则直接返回。

        if(fast == null){
                return  null;
            }

代码实现

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k <= 0) return null;//当链表为null时，直接返回
        
        ListNode slow = head;
        ListNode fast = head;
        int i = k-1;
        while(i > 0){
            i--;
            fast = fast.next;
            if(fast == null){
                return  null;//当fast为null时，说明k不合法
            }
        }
 
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow; 
        
    }
}