本文共 975 字，大约阅读时间需要 3 分钟。

在线题目链接：

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

3 总结

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

探讨学习加：

转载地址：https://lyy-0217.blog.csdn.net/article/details/85109677 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！