题解 | #链表中倒数最后k个结点#

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
*/
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    // 快慢指针，快指针先走 k 步，当快指针指向链表尾部时，慢指针刚好指向倒数第 k 个节点
    slow, fast := pHead, pHead

    for k > 0  {
        if fast != nil {
            fast = fast.Next
        } else {
            return nil  
        }
        k--
    }

    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    return slow
}

1. 快指针先移动 k 步，移动过程判断快指针是否为 nil（如果为 nil，说明链表长度小于 k）；
2. 以快指针为遍历指针，快慢指针同时移动，直至快指针指向 nil，此时慢指针指向倒数第 k 个节点；
3. 下图借用牛客 java 解题思路的图（盗用）