剑指Offer——链表中倒数第 K 个结点

题目描述

输入一个链表，输出该链表中倒数第 k 个结点。
时间限制：1 秒 空间限制：32768K
本题知识点： 链表

代码实现

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode node = head, temp = head;
        int i = 0;
        for(; node != null; i++){
            if(i >= k){
                temp = temp.next;
            }
            node = node.next;
        }
        return k > i ? null : temp;
    }
}

解题思路

首先我们要知道什么是链表，可以通过参考文章底部的推荐文章进行了解。简单来说就是它有一系列结点组成，每个结点包括一个数据结构（用来存放各类型的数据），还包括一个指向下一个结点的指针。

因为题中给出的链表为单链表，每个结点只有下一个结点的指针，而没有前一个结点的指针，所以我们要想知道倒数第 k 个结点，我们首先需要从第一个结点开始一直找到最后一个结点，得到共有多少个结点，然后再算出倒数第 k 个结点是整数第几个结点，然后再从第一个结点开始直到找到最终要找的结点。

但是我们这里使用的方法很巧妙，我们定义两个指针都指向第一个结点，然后让其中一个指针 node 先走 k 步，然后 temp 指针再开始走，直到 node 走到最后，因为 node 比 temp 始终快 k 步，所以最后 temp 指向的结点就是倒数第 k 个结点，不过这里有个前提就是 k 不能大于我们所有结点的总数，如果大于的话，是没有倒数第 k 个结点的，所以返回空。