首页 > 试题广场 >

链表中倒数最后k个结点

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

热度指数：405890 时间限制：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

面向对象的鳄鱼很想喝咖啡

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;
        }
        ListNode current = pHead;
        ListNode pre = null;
        while (current != null){
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        ListNode currentPre = pre;
        ListNode prePre = null;
        for (int i = 1; i<=k; i++){
            if (currentPre == null){
                return null;
            }
            ListNode next = currentPre.next;
            currentPre.next = prePre;
            prePre = currentPre;
            currentPre = next;
        }
        return prePre;
    }
}
倒序两遍解决

发表于 2025-04-23 11:22:12 回复(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 pHead;
        }
        if (k == 0)
        {
            return null;
        }
        ListNode pNode = pHead;
        ListNode sNode = pHead;
        for (int i = 0; i < k - 1; i++)
        {
            sNode = sNode.next;
            if (sNode == null)
            {
                return null;
            }
        }
        while (sNode.next != null)
        {
            pNode = pNode.next;
            sNode = sNode.next;
        }
        return pNode;
    }
}

发表于 2025-04-07 14:39:10 回复(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 (k == 0)

{

return null;

}

List<Integer> s = new ArrayList<>();

while (pHead != null)

{

s.add(pHead.val);

pHead = pHead.next;

}

if (k > s.size())

{

return null;

}

// List<Integer> collect = s.stream().skip(k + 1).collect(Collectors.toList());

List<Integer> collect = new ArrayList<>();

for (int i = s.size() - k; i < s.size(); i++)

{

collect.add(s.get(i));

}

if (collect.size() != 0) {

ListNode dummy = new ListNode(collect.get(0));

ListNode cur = dummy;

for (int i = 1; i < collect.size(); i++) {

cur.next = new ListNode(collect.get(i));

cur = cur.next;

}

return dummy;

}

else

{

ListNode dummy = new ListNode(s.get(0));

ListNode cur = dummy;

for (int i = 1; i < s.size(); i++) {

cur.next = new ListNode(s.get(i));

cur = cur.next;

}

return dummy;

}

发表于 2024-10-24 20:53:01 回复(0)

Java

牛客348570162号

public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode return_head = pHead;
        while(pHead != null && k-- >0 ){
            pHead = pHead.next;
        }
        if(k>0) return null;
        while(pHead != null){
            pHead = pHead.next;
            return_head = return_head.next;
        }
        return return_head;
    }

发表于 2024-08-17 13:00:16 回复(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

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.遍历一遍链表，得到总共有几个结点
        if (pHead == null) {
            return null;
        }
        // 确保至少有一个结点
        int num = 0;
        ListNode cur = pHead;
        while (cur != null) {
            num++;
            cur = cur.next;
        }

        // 2.总结点数 - k，得到第二次遍历的索引
        int index = num - k;
        ListNode result = null;
        // 3.返回索引处的结点
        if (index < 0) {
            // 3.1 index < 0 - 说明链表长度不够
            result = null;
        } else if (index == 0) {
            // 3.2 index = 0 - 正好需要整个链表
            result = pHead;
        } else {
            // 3.2 index > 0 - 找到index处的结点的下一个，可以直接返回
            cur = pHead;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            result = cur;
        }
        return result;
    }
}

发表于 2024-07-26 23:15:05 回复(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;

List<ListNode> list=new ArrayList<>();

while(pHead!=null){

list.add(pHead);

pHead=pHead.next;

}

if(list.size()-k<0||k==0)return null;

return list.get(list.size()-k);

}

发表于 2024-07-25 19:58:45 回复(0)

Java

旭源

public ListNode FindKthToTail (ListNode pHead, int k) {

// write code here

ListNode pre = pHead;

ListNode back = pHead;

for(int i = 0;i<k;i++){

if(pre==null) return null;

pre = pre.next;

}

while(pre!=null&&back!=null){

pre = pre.next;

back = back.next;

}

return back;

}

发表于 2024-06-29 20:39:50 回复(0)

Java

saliy

第一种，最直白的方法，不过效率不好

public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead==null){
            return null;
        }
        //算列表有多少元素
        ListNode dummy=pHead;
        ListNode index=pHead;
        int count=0;
        while(dummy!=null){
            dummy=dummy.next;
            count++;
        }
        if(k>count){
            return null;
        }
        //倒数第K个元素，正数为n-k+1个元素。
        int found=count-k;
        while(found>0){
            index=index.next;
            found--;
        }      
        return index;
    }

发表于 2024-06-23 12:13:23 回复(0)

Java

PeterLee6688

   public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int size = 0;
        if(pHead == null) return null;
        ListNode one = pHead;
        ListNode two = pHead;
        while(two!= null){
            size++;
            one = one.next;
            if(size > k){
                // one指针到K个位子了，说明two指针该开始动了
                two = two.next;
            }
            if(one == null){
                break;
            }
            
        }
        if(size < k){
            return null;
        }
        return two;
    }

发表于 2024-05-14 16:43:35 回复(0)

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)

提交观点

问题信息

链表

上传者：灵溪吴彦祖

难度：

120条回答 826收藏 8067浏览

通过挑战的用户

查看代码

牛客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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题