【剑指Offer】链表中倒数第k个结点

题目描述

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

解法

基本思路是使用两个辅助指针p, q，让p先走k - 1步后，p, q两个指针再一起走
这样当p指针走到链表的末尾时，q指针刚好走到的就是倒数第k个结点
如下图所示

实现代码

public ListNode FindKthToTail(ListNode head, int k)
{
    ListNode p = head, q = null;
    while(p != null){
        if(q != null)
            q = q.next;
        else if(--k == 0)
            q = head;
        p = p.next;
    }
    return q;
}

更多算法题目的完整描述，AC代码，以及解题思路可以查看GitHub仓库Algorithm