首页 > 试题广场 >

链表中倒数最后k个结点

[编程题]链表中倒数最后k个结点

热度指数：358587 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个长度为 n 的链表，设链表中的元素的值为 a_i ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围： $0 \leq n \leq 10^5$ ， $0 \leq a_i \leq 10^9$ ， $0 \leq k \leq 10^9$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1

输入

{1,2,3,4,5},2

输出

{4,5}

说明

返回倒数第2个节点4，系统会打印后面所有的节点来比较。

示例2

输入

{2},8

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Java

早秋

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode pre=pHead;
        ListNode back=pHead;
        if(pHead==null){
            return null;
        }
        for(int i=0;i<k;i++){
            if(pre!=null){
              pre=pre.next; 
            }
            else{
                return null;
            }      
        }
        while(pre!=null){
            back=back.next;
            pre=pre.next;
        }
        return back;
    }

编辑于 2024-03-07 23:47:17 回复(0)

Java

牛客203756367号

利用map集合

1.遍历链表将其所有加入到map集合中 key为顺序

2.再通过获取map集合的长度得到链表的长度 - (k-1)即可

 /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        Map<Integer,ListNode> maps = new HashMap<>();
        ListNode valNode = pHead;
        int index = 1;
        while(null != valNode){
            maps.put(index++,valNode);
            valNode = valNode.next;
        }
        return maps.get(maps.size() - (k - 1));
    }

发表于 2024-02-04 15:38:40 回复(1)

Java

牛客520167023号

public class Solution {
    /**
     * 双指针
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int count = 0;
        ListNode fir = pHead,sec = pHead;
        while(fir != null){
            fir = fir.next;
            if(count >= k){
                sec = sec.next;
            }
            count++;
        }
        if(count < k) return null;
        return sec;
    }
}

发表于 2023-12-12 20:46:52 回复(0)

Java

阿mini默

public ListNode FindKthToTail (ListNode pHead, int k) {
    // write code here
    ListNode fast = pHead;
    ListNode slow = pHead;
    for(int i=0; i<k; i++){
        if(fast == null){
            return null;
        }
        fast = fast.next;
    }
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
}

编辑于 2023-12-05 19:05:39 回复(0)

Java

想吃火锅的花生米

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ArrayList<ListNode> res = new ArrayList<>();
        // write code here
        while (pHead != null) {
            res.add(pHead);
            pHead = pHead.next;
        }
        if (res.size() < k||k==0) return  null;
        return res.get(res.size() - k);
    }
}

发表于 2023-11-23 15:16:31 回复(0)

Java

求知心态

public ListNode FindKthToTail (ListNode pHead, int k) {
        ArrayList<ListNode> nodeLists = new ArrayList<>();
        while (pHead!=null){
            nodeLists.add(pHead);
            pHead=pHead.next;
        }
        if (nodeLists.size()<k||k==0){
            return null;
        }
        else {
            return nodeLists.get(nodeLists.size()-k);
        }
    }

发表于 2023-10-16 22:24:39 回复(0)

Java

夹仲见歌

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode fl = pHead;
        while(fl!=null){
            fl = fl.next;
            n++;
        }
        ListNode res = pHead;
        if(n<k)return null;
        if(n==k)return pHead;
        for(int i = 0;i<n-k;i++){
            res = res.next;
        }
        return res;
    }
}

发表于 2023-09-17 13:49:16 回复(0)

Java

光恰似水

  ListNode dummyNode = new ListNode(0);
        dummyNode.next = pHead;
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        for ( int i = 0; i < k; i++) {
            if (fast != null && fast.next != null) {
                fast = fast.next;
            }else{
                    return slow = null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.next;
    }

加入虚拟节点 殊途同归

发表于 2023-09-12 20:30:47 回复(0)

Java

dqxfz

public ListNode FindKthToTail (ListNode pHead, int k) {

ListNode kHead = pHead;

int kSize = 0;

while (pHead != null) {

if (kSize == k) {

kHead = kHead.next;

} else {

kSize++;

}

pHead = pHead.next;

}

if (kSize != k) {

return null;

}

return kHead;

}

发表于 2023-09-08 15:21:01 回复(0)

Java

牛客101757813号

感觉写链表要和list杠上了

public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        List<ListNode> list = new ArrayList<>();
        while(pHead != null){
            list.add((pHead));
            pHead = pHead.next;
        }
        int index = list.size() - k;
        if(index < list.size() && index >= 0){
            return list.get(index);
        }
        return null;
    }

发表于 2023-08-03 11:09:45 回复(0)

Java

做则必成的勇气和信心

public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast=pHead;
        ListNode slow=pHead;
        ListNode forLength=pHead;
        int length=0;
        while(forLength!=null){
            forLength=forLength.next;
            length++;
        }
        if(length<k){
            return null;
        }
      
        while(fast!=null&&k-->0){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

发表于 2023-07-17 20:10:58 回复(0)

Java

帅气的小熊猫在学习

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        // 快慢指针，fast比slow先走k个节点，再同步走，当 fast == null 时
        // slow刚好指向倒数第k个节点
        ListNode slow, fast;
        slow = fast = pHead;
        while (k-- != 0) {
            if (fast == null) {
                // 如果链表元素少于 k 个，则直接返回
                return null;
            }
            fast = fast.next;
        }
        // 开始同步移动
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

发表于 2023-07-12 23:14:57 回复(0)

Java

抓住努力的尾巴

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //判断头节点是否为空
        if (pHead == null) {
            return null;
        }
        //判断K是否合法
        if (k <= 0) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (k - 1 != 0) {
            if (fast.next != null) {
                fast = fast.next;
                k--;
            } else {
                return null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

发表于 2023-07-10 12:41:04 回复(0)

Java

牛客64578110号

给大家提供一种简单易懂的方法

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int len = getLen(pHead);
        if(k == len) {
            return pHead;
        }
        while(pHead != null) {
            pHead = pHead.next;
            len--;
            if(len == k) {
                return pHead;
            }
        }
        return null;
    }

    public static int getLen(ListNode head) {
        if (head == null) {
            return 0;
        }
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
}

发表于 2023-07-05 15:48:48 回复(0)

Java

牛客839384289号

public ListNode FindKthToTail (ListNode pHead, int k) {
    // write code here
    ListNode p1=pHead ,p2=pHead;
    while(p2!=null && k-->1){
        p2=p2.next;
    }
    while(p2!=null && p2.next!=null){
        p1=p1.next;
        p2=p2.next;
    }
    return k==0?p1:null;
}

发表于 2023-07-01 16:06:14 回复(0)

Java

牛客080119号

public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //计算列表的长度
        ListNode head=pHead;
        int n=0;
       while(head!=null){
        head=head.next;
        n++;
       }
       //判断列表是否为空
       head=pHead;
       if(k>n)
       return null;
        //不为空的话，返回头指针
       for(int i=1;i<=n-k;i++){
        head=head.next;
       }
       return head;
    }

发表于 2023-03-30 21:03:39 回复(0)

提交观点

问题信息

链表

上传者：灵溪吴彦祖

难度：

111条回答 717收藏 5803浏览

通过挑战的用户

查看代码

牛客47096...

2023-03-09 21:38:33
cdjb

2023-02-07 00:21:31
Chensp

2023-01-31 15:47:21
Zhaaaaaaa

2023-01-19 21:46:58
Y/B＆P!

2023-01-07 10:56:20

链表中倒数最后k个结点

输入

输出

说明

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题