[数据结构与算法]剑指Offer - 14_链表中倒数第k个节点

题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例

输入: 1->2->3->4->5, k = 2.
返输出：4->5.

思路

1. 采用快慢指针，先上快指针找到第k个位置，当在寻找第k个时，如果出现了null，那直接返回null
2. 快指针指向第k个，慢指针指向头结点，那么快慢指针就间隔了k个结点
3. 所以当快指针遍历结束，那倒数第k个就是慢指针处，那么直接返回慢指针即可

Code

public class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (null == head) {
            return null;
        }
        //找到第k个结点位置，如果中间存在是null情况，直接返回
        ListNode fastNode = head;
        for (int i = 0; i < k; i++) {
            if (null == fastNode) {
                return null;
            }
            fastNode = fastNode.next;
        }
        //慢指针指向头结点
        ListNode slowNode = head;
        //从快指针开始遍历，知道遍历结束
        while (null != fastNode) {
            //快慢指针都指向下一个结点
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        //返回慢指针
        return slowNode;
    }
}