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

╰半夏微凉° 2022-02-28 13:16 221阅读 0赞

## 题目描述 ##

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

初步解题思路：先求出链表总长，再从头遍历到倒数第k个结点。  
**最优解：这个想法很巧妙。因为求得是倒数第k个，所以设置两个头指针，一个先走到k个结点，然后两个指针同时走，当第一个指针走完为null时，第二个指针也走到了倒数第k个结点（第二个指针还剩k个结点）。**

## Java初步解题 ##

/*
    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 dummy = null;
            dummy = head;
            int count = 0;
            if(head == null)
                return null;
            while(dummy!=null){
                count++;
                dummy = dummy.next;
            }
            if(count<k)
                return null;
            int i = 0;
            while(i<(count-k)){
                head = head.next;
                i++;
            }
            return head;
        }
    }

## 最优解 ##

public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            ListNode pre = head, result = head;
            int count=0;
            while(pre!=null){
                pre = pre.next;
                if(count>=k)
                    result = result.next;
                count++;
            }
            if(count<k)
                return null;
            return result;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指Offer】22. 链表中倒数第 K 个结点

[NowCoder][] 题目描述输入一个链表，输出该链表中倒数第k个结点。解题思路设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K

雨点打透心脏的1/2处/ 2022年11月25日 13:08/ 0 赞/ 12 阅读

相关剑指Offer-链表中倒数第k个结点

链表中倒数第k个结点题目描述：输入一个链表，输出该链表中倒数第k个结点。解题思路：采用快慢指针方法，先让a指针前进k步，然后ab指针一同前进，

Myth丶恋晨/ 2022年08月04日 12:50/ 0 赞/ 144 阅读

相关剑指Offer | 链表中倒数第k个结点

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

古城微笑少年丶/ 2022年05月24日 03:44/ 0 赞/ 167 阅读

相关剑指offer:链表中倒数第k个结点

题目描述输入一个链表，输出该链表中倒数第k个结点。 AC C++ Solution: 使用双指针法,一个指针先移动k-1步, 然后同时移动, 快指针到达链表末尾时,

àì夳堔傛蜴生んèń/ 2022年04月10日 07:54/ 0 赞/ 164 阅读

相关【剑指offer】链表中倒数第k个结点

链表中倒数第k个结点题目描述输入一个链表，输出该链表中倒数第k个结点。解题思路设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后两个指针同

忘是亡心i/ 2022年04月08日 17:11/ 0 赞/ 279 阅读

相关【剑指Offer】（链表）链表中倒数第k个结点

题目链接：[https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11

迷南。/ 2022年03月17日 14:20/ 0 赞/ 153 阅读

相关剑指Offer-链表中倒数第k个结点

题目描述输入一个链表，输出该链表中倒数第k个结点。初步解题思路：先求出链表总长，再从头遍历到倒数第k个结点。最优解：这个想法很巧妙。因为求得是倒数第k个，所以

╰半夏微凉°/ 2022年02月28日 13:16/ 0 赞/ 222 阅读

相关链表第倒数K个结点-剑指offer-Java

题目描述：输入一个链表，输出该链表中倒数第k个结点。解题思路：使用两个指针，初始化两个指针都带head，然后将其中一个指针移动k-1步，移动到k个结点的部分，然后两个结点一

快来打我*/ 2021年12月10日 09:43/ 0 赞/ 174 阅读

相关剑指offer链表中倒数第k个结点

题目:输入一个链表，输出该链表中倒数第K个节点；为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个结点。题目分析： ![在这里插入图

素颜马尾好姑娘i/ 2021年09月19日 18:38/ 0 赞/ 379 阅读

相关剑指offer：链表中倒数第k个结点

试题：输入一个链表，输出该链表中倒数第k个结点。代码：很巧妙的思想，使用一个指针先走k-1步是的p与q相距k个节点。然后两个指针一直往下走，知道探底。 /

我不是女神ヾ/ 2021年06月24日 16:00/ 0 赞/ 360 阅读