1 题目描述

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

2 题目分析

这道题比较简单。常规做法是先求出链表的总的节点个数n，然后再从头开始找第n-k+1个节点，这个节点就是倒数第k个节点。这种方法很好实现。

还有一种比较巧妙的解法：指定两个指针p和q指向链表头，让p先走k-1步，然后当p走了k-1步之后，q也开始从头开始往后走。那么此时p与q之间的距离为k-1。当p走到链表的末尾后，因为q与p距离k-1，所以q刚好在倒数第k个位置。
如下图

假设上面是需要找到倒数第3个节点。先让p1走3-1=2步，然后p2与p1同步开始跑，当p1到最后一个节点时，p2刚好位于倒数第3个节点。

2.1 Java代码

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p, q;
        p = q = head;
        int i = 0;
        for (; p != null; i++) {
            if (i >= k)
                q = q.next;
            p = p.next;
        }
        return i < k ? null : q;
    }
}

2.2 C++代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* p=pListHead,*q=pListHead;
        int i=0;
        for(;p!=nullptr;i++){
            if(i>=k)q=q->next;
            p=p->next;
        }
        return i<k?nullptr:q;    
    }
};

3 总结

常规做法比较简单好想，使用两个指针前后移动这种方法更加高效

探讨学习加：
个人qq：1126137994
个人微信：liu1126137994