首页 > 试题广场 >

链表中倒数最后k个结点

[编程题]链表中倒数最后k个结点
  • 热度指数:352320 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。


数据范围:
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度

例如输入{1,2,3,4,5},2时,对应的链表结构如下图所示:
其中蓝色部分为该链表的最后2个结点,所以返回倒数第2个结点(也即结点值为4的结点)即可,系统会打印后面所有的节点来比较。
示例1

输入

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

输出

{4,5}

说明

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

输入

{2},8

输出

{}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#

# @param pHead ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        if pHead is None:
            return pHead
        len1 = 0
        p = pHead
        while pHead is not None:
            len1 = len1+1
            pHead = pHead.next
            
        if k > len1:
            return pHead
        elif k == len1:
            return p
        else:
            for i in range(len1-k):
                p = p.next
        return p
            
            
发表于 2021-08-04 23:22:21 回复(0)
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
        //方法1
//         ListNode cur = new ListNode(1);
//         cur.next = pHead;
//         int len = 0;
//         while(pHead != null){
//             len+=1;
//             pHead = pHead.next;
//         }

//         int time = len-k;
//         if(time<0){
//             return null;
//         }
//         cur = cur.next;
//         for(int i=0;i<time;i++){
//             cur = cur.next;
//         }
//         return cur;
        //方法2 快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        //快指针先走k步
        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;
    }
}
搞不懂第一个笨办法竟然比快慢指针时间短,占用少
发表于 2022-06-02 15:53:05 回复(0)
class Solution:
    def FindKthToTail(self, pHead, k):
        if k <= 0&nbs***bsp;not pHead:
            return None
        # 快慢指针
        slow = fast = pHead
        while k > 1:
            fast = fast.next
            if not fast:
                return None
            k -= 1

        while fast.next:
            slow = slow.next
            fast = fast.next

        return slow

发表于 2021-07-31 09:37:58 回复(0)
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) {
        //使用双指针后移找到倒数第k个节点,先让p1(p1=pHead)指针移动k个节点,然后p2(p2=pHead)和p1一起后移
        //直到p1为空为止,p2指针指向的就是倒数第k个节点的位置
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        int length = 0;
        while(pHead!=null){
            length++;
            pHead = pHead.next;
        }
        if(k==0 || k > length){
            return null;
        }
        for(int i=1;i<=k;i++){
            p1 = p1.next;
        }
        while(p1!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}
    /*遍历链表,计算链表的长度length,然后用头节点向后移动length-k次,就得到了倒数第k个节点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode ptemp = pHead;
        ListNode p = pHead;
        int length = 0;
        while(ptemp!=null){
            length++;
            ptemp = ptemp.next;
        }
        if(length<k){
            return null;
        }
        for(int i=1;i<=length-k;i++){
            p = p.next;
        }
        return p;
    }
}
*/
发表于 2021-06-09 17:01:17 回复(0)
运行时间:15ms
超过29.16%用Java提交的代码
占用内存:11300KB
超过38.48%用Java提交的代码
暴力
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
         ListNode cur = pHead;
        int size = 0;
        while (cur != null) {
            cur = cur.next;
            size++;
        }
        if (k > size) return null;
        int n = size - k;
        ListNode temp=pHead;
        for (int i = 0; i < n; i++) {
            temp=temp.next;
        }
        return temp;
    }
}

发表于 2021-04-11 00:06:08 回复(0)
 public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead==null) return null;
        ListNode fast=pHead;
        while(fast!=null&&k>0){
            fast=fast.next;
            k--;
        }
        if(k>0) return null;//说明不够k个
        ListNode slow=pHead;
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

发表于 2021-04-02 09:14:25 回复(1)
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(pHead === null){
        return null;
    }else{
        var cur1 = pHead,
            cur2 = pHead,
            newList = [],
            length = 0;
        while(cur1){
            cur1 = cur1.next;
            length++;
        }
        if(k > length || k <= 0){
            return null;
        }
        if(k == length){
            return pHead;
        }else{
            for(var i = 0;i < length - k;i++){
                cur2 = cur2.next;
            }
            newList.push(cur2.val);
        }
        return cur2;
     }
}
对链表不熟,写的好复杂,以后优化一下。
有个疑问就是,我的return cur2,一直打印的是当前节点之后的所有节点,比如输入{1,2,3,4,5},2,打印出来的是{4,5},为什么这样也对呢,我不是很理解,请各位帮忙指点一下~

发表于 2021-03-22 13:09:35 回复(2)
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;
        } 
        Queue<ListNode> q = new LinkedList<>();
         ListNode listNode = pHead;
        int i=0;
        while(pHead!=null){
            q.add(pHead);
            i++;
            pHead = pHead.next;
            if(i==k){
                if(pHead==null) return listNode;
                i--;
                listNode = listNode.next;
            }
        }
       if(i<k) return null;
        return listNode;
    }
}

发表于 2021-03-10 14:34:39 回复(0)
class Solution:
    # 方法一:两次从左到右遍历链表,第一次获取长度,第二吃获取目标值, 时间复杂度为O(n),代码繁琐
    def FindKthToTail(self , pHead , k ):
        if not pHead:
            return pHead
        if k <= 0:
            print("Value of k must be positive")
            return None
        # 计算链表长度
        length = 0
        p = q = pHead
        while p:
            length += 1
            p = p.next
        if k > length:
            print("Value of k is greater than length of list")
            return None
        else:
            while q and length != k:
                length = length - 1
                q = q.next
            return q

     # 方法二:双指针法,前一个指针先走k步,后一个指针再走(链表长度-k)步
     def FindKthToTail(self , pHead , k ):
#           # 链表为空
            if not pHead or k<0:
                return pHead
            # 链表只有一个结点
            if pHead and not pHead.next:
                if k > 1:
                    print("Value of k is greater than length of list")
                    return pHead.next
                else:
                    return pHead
            # 链表包含两个或两个以上结点
            prev = post = pHead
            for i in range(k):
                # 每走一步判断是否走过的步数大于链表长度,若大于,则返回空
                if not prev:
                    return prev
                prev = prev.next
           # 走过的步数k < 链表长度
            while prev:
                prev = prev.next
                post = post.next
           # 走过的步数k = 链表长度
            return post
发表于 2021-03-07 00:30:52 回复(0)
分享一个和双指针不同的,思路类似JZ-15。先用递归到链表最后,然后用一个cnt记录往回走了多少个节点,当cnt等于k时用out记录下来,最后输出out。
运行时间:3ms
超过60.06%用C++提交的代码
占用内存:384KB
超过56.86%用C++提交的代码
class Solution {
    int cnt=0;
    ListNode* out=NULL;
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        if (pHead==NULL||pHead->next==NULL){
            cnt++;
            if (cnt==k){
                out=pHead;
            }
            return pHead;
        }
        ListNode * tmp = FindKthToTail(pHead->next,k);
        cnt++;
        if (cnt==k){
                out=pHead;
            }
        return out;
    }
};


发表于 2021-04-12 12:07:51 回复(2)
[Java]
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead==null || k<=0)
             return null;
        ListNode fast=pHead;
        while(k>1 && fast!=null) {
            fast=fast.next;
            k--;
        }
        if(fast==null) {
            return null;//链表长度不足k个
        }
        ListNode low=pHead;
        while(fast.next!=null) {
            fast=fast.next;
            low=low.next;
        }
        return low;
    }
}


发表于 2021-03-16 11:56:24 回复(0)
双指针,一根指针先走k步(边走边判断是否为空,因为链表长可能小于k),最后两根指针一起走,前面那根指针为空时后面的指针所指即为所求
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        if(nullptr == pHead || k <= 0)
            return nullptr;
        ListNode *p = pHead, *q = pHead;
        while(nullptr != p && k)
        {
            --k;
            p = p->next;
        }
        if(k)
            return nullptr;
        while(p)
        {
            p = p->next;
            q = q->next;
        }
        return q;
    }
};

发表于 2021-03-01 11:20:25 回复(1)
快慢指针,判断好特殊情况:
  • 空链表
  • k大于链表的节点数量
class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        if not pHead:
            return None
        fast, slow = pHead, pHead
        while fast and k > 0:
            fast = fast.next
            k -= 1
        if k > 0:
            return None
        while fast:
            fast = fast.next
            slow = slow.next
        return slow
时间复杂度:O(N)。
空间复杂度:O(1)。
编辑于 2021-02-28 14:50:40 回复(3)
js
双指针,定于两个指针fast和slow,让fast先跑k步,然后slow和fast同时开始跑,当fast为null时,slow的值就是第k个节点,输出slow即可。这个过程画个图就很清晰明了了。

这一过程大多数人都会做,主要是边界条件不要忘了判断。

<1>当链表为空时,当k <= 0时,都要输出为空
<2>当链表长度小于k时,输出为空。如果k大于链表长度,根据前面写好的程序可以得知,此时的fast已经为null了,而i却还小于k,所以直接在最后面加个判断语句就行了。
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(!pHead || k <= 0){ //判断边界条件
        return null;
    }
    var i = 0; //用来判断fast跑了多少步
    var fast = pHead;//定义双指针
    var slow = pHead;
    while(fast){     //当fast变成null时,结束循环
        fast = fast.next;
        if(i >= k){    //判断fast是否已经跑了k步
            slow = slow.next;
        }
        i++;
    }
    if(i < k){      //判断链表长度是否小于k
        return null;
    }else{
        return slow;
    }
}



编辑于 2021-03-26 10:35:46 回复(0)
解题思路:快慢指针,先让一个指针指向头节点,先走K步,如果为空就返回空,反之,就再让一个指针从头节点出发,快慢指针一起走,直到快指针为空,输出慢指针
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;
        ListNode fast=pHead;
        int i=0;
        while(i<k){
            if(fast==null) return fast;
            fast=fast.next;
            i++;
        }
        ListNode slow=pHead;
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}


发表于 2021-03-20 15:17:55 回复(0)
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    struct ListNode* fast=pHead;
    struct ListNode* slow=pHead;
    for(int i=0;i<k;i++)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}
发表于 2023-09-06 15:53:09 回复(0)
简介的JavaScript:
function FindKthToTail( pHead ,  k ) {
    // write code here    
    if (pHead === null || k === 0) return null;
    
    let node = pHead;
    for(let i = 1; i < k; i++){
        pHead = pHead.next;
        if (pHead === null) return null;
    }
    
    while (pHead.next){
        node = node.next;
        pHead = pHead.next;
    }
    
    return node;
}


发表于 2021-09-29 03:32:05 回复(2)
// 需要遍历两次,第一次记个数,第二次找倒数
    public ListNode FindKthToTail(ListNode pHead, int k) {

        if (pHead == null || k == 0) {
            return null;
        }

        int count = 0;

        ListNode temp = pHead;

        while (temp!=null) {
            count ++ ;
            temp = temp.next;
        }

        if (count < k) {
            return null;
        }

        temp = pHead;

        for (int i = 0; i < count - k; i++) {
            temp = temp.next;
        }

        return temp;
    }

发表于 2021-05-04 17:49:15 回复(0)
ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode* p(pHead),* q(pHead);
        while(k&&q){
            q = q->next;
            k--;
        }
        if(k) return {};
        while(q){
            p = p->next;
            q = q->next;
        }
        return p;
    }


发表于 2021-03-04 21:35:21 回复(1)
使用JavaScript实现:

思路:使用快慢指针
  1. 设置两个“指针”,一个快指针fast,一个慢指针slow,初始时两个指针都指向头节点
  2. 让快指针fast先向前走K步,慢指针slow不动。如果快指针走的过程中自己变成null了,说明链表的长度小于K,直接返回null即可。
  3. 然后快指针和慢指针同时向前移动。等fast为null的时候,两个指针都往前走了(链表长度-K)步,停止移动。此时慢指针slow所在的位置就是链表中倒数第K个位置。直接返回slow即可
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
function FindKthToTail( pHead ,  k ) {
    // write code here
    let fast = pHead;
    let slow = pHead;
    let count = 0;
    while(count++ < k) {
        if(fast === null) return null;
        fast = fast.next;
    }
    while(fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}
module.exports = {
    FindKthToTail : FindKthToTail
};

发表于 2021-07-24 15:49:21 回复(0)