【面试题14-链表中倒数第k个结点】

剑指offer第十四题。

题目描述

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

解题思路

做过这个题目或者了解过，思路一下就有了。要求倒数第k个结点，而这个单向链表只能next，所以往前找是不行的。怎么办呢？我们可以先派一个指针走k个结点，然后另一个指针从头开始，两个指针同时后移，当前面个指针到最后一个结点的下一个结点即null的时候，后面个指针恰好指向的就是倒数第k个结点。

我的答案

答案稍微有点繁琐了，但是我觉得思路清晰是最重要的，代码再精简是需要在思路清晰的基础上再加以磨练才行。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null){
            return null;
        }
        
        //计算出链表的长度，判断k是否超出
        int count = 0;
        ListNode tmp = head;
        while(tmp != null){
            count++;
            tmp = tmp.next;
        }
        
        if(k > count){
            return null;
        }
        
        //找到第k个结点
        ListNode node = head;
        while(k > 0){
            node = node.next;
            k--;
        }
        
        //一个结点指向head，一个结点指向第k个，两者同时后移
        while(node != null){
            head = head.next;
            node = node.next;
        }
        
        //此时ehad就是倒数第k个结点
        return head;
    }
}