首页 > 试题广场 >

链表中倒数最后k个结点

[编程题]链表中倒数最后k个结点
  • 热度指数：358733 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Javascript
牛客661815010号头像 牛客661815010号
function FindKthToTail(pHead, k) {
  // write code here
  let l = 0;
  let start = pHead;
  // 获取链表长度
  while (start) {
    start = start.next;
    l++;
  }
  // 通过链表长度来减去k值来返回倒数的第k的结点，若链表长度比k值则返回null
  if (l >= k) {
    for (let i = 1; i <= l - k; i++) {
      pHead = pHead.next;
    }
    return pHead;
  } else {
    return null;
  }
}
module.exports = {
  FindKthToTail: FindKthToTail,
};


发表于 2022-07-10 13:09:43 回复(0)
Javascript
越过森林越过风头像 越过森林越过风 
/*
 * 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 len=0;
    let p1=pHead;
    for(let i=0;i<k;i++){
        if(p1===null){
            return null;
        }
        p1=p1.next;
    }
    p1=pHead;
    let len1=0;
    while(p1){
        len1++;
        p1=p1.next;
    }
    p1=pHead;
    let len2=len1-k;
    while(len2--){
        p1=p1.next;
    }
    return p1;
}
module.exports = {
    FindKthToTail : FindKthToTail
};

发表于 2022-05-03 10:11:58 回复(0)
Javascript
Seayeee头像 Seayeee 
/*
 * 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 p1 = pHead, p2 = pHead
    if(!pHead){
        return null
    }
    if(k <= 0){
        return null
    }
    while(p1 && k>0){
        p1 = p1.next
        k--
    }
    if(k>0){
        return null
    }
    while(p1){
        p1 = p1.next
        p2 = p2.next
    }
    return p2
    
}
module.exports = {
    FindKthToTail : FindKthToTail
};

发表于 2022-04-15 00:29:23 回复(0)
Javascript
A-成都搬砖日结包吃不包住头像 A-成都搬砖日结包吃不包住
更好的表示 
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(!pHead||!k) return null
    let p1 = pHead, p2 = pHead, count = 1;
    while(count<k){
        // 证明 k 范围过大
        if(!p2.next) return null
        p2 = p2.next;
        count++;
    }
    while(p2.next){
        p2 = p2.next
        p1 = p1.next
    }
    return p1
}


发表于 2022-03-07 21:39:55 回复(0)
Javascript
toope头像 toope 
// 直接解法，先求出链表长度，然后再重新遍历

function FindKthToTail( pHead ,  k ) {
    var length = 0;
    var i = 0;
    var cur = pHead;
    while(pHead){
        pHead = pHead.next;
        length ++;
    }
    if(k > length)return null;
    while(cur && i < length - k) {
        cur = cur.next;
        i ++;
    }
    return cur;
}
module.exports = {
    FindKthToTail : FindKthToTail
};

发表于 2022-03-06 10:11:07 回复(0)
Javascript
FoRtCurious头像 FoRtCurious
性能相比有点差... 
function FindKthToTail( pHead ,  k ) {
    // write code here
    let stack = [];
    let head = {
        val:0,
        next: null
    }
    while(pHead) {
        stack.push(pHead);
        pHead = pHead.next
    }
    if (stack.length === 0 || stack.length < k) return null;
    for (let i=0; i<k; i++) {
        head.next = stack.pop();
    }
    return head.next
}


发表于 2021-12-12 14:43:16 回复(0)
Javascript
Elegy201905242021282头像 Elegy201905242021282
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(!pHead || !k) return null
     let front = pHead;
      let behind = pHead;
      let index = 1;
      while (front.next) {
        index++;
        front = front.next;
        if (index > k) {
          behind = behind.next;
        }
      }
      return (k <= index) && behind;
}
module.exports = {
    FindKthToTail : FindKthToTail
};
发表于 2021-12-07 14:48:14 回复(0)
Javascript
takeheart莹头像 takeheart莹
// 方法一：遍历两次，第一次记个数，第二次找倒数
function FindKthToTail ( pHead ,  k ) {
    if (!pHead) return null
    if (k <= 0) return null
    let p = pHead
    let n = 0
    while (pHead) {
        pHead = pHead.next
        n++
    }
    if (n < k) return null
    // 获取到总数n了
    let i = 0
    while (i < n - k && p) {
        p = p.next
        i++
    }
    return p
}
// 方法二：双指针，定于两个指针fast和slow，
// 让fast先跑k步，然后slow和fast同时开始跑，
// 当fast为null时，slow的值就是第k个节点，输出slow即可。
function FindKthToTail2 (pHead ,  k ) {
    if (!pHead) return null
    if (k <= 0) return null
    let i = 0
    let slow = pHead
    let fast = pHead
    // fast先跑k步
    while (i < k && fast) {
        fast = fast.next
        i++
    }
    if (i < k) return null // pHead长度没有k大
    // 等fast一直到null，说明已经跑了(n-k)步，则slow此时就是倒数k个节点：
    while (fast) {
        fast = fast.next
        slow = slow.next
    }
    return slow
}

发表于 2021-10-07 16:37:05 回复(0)
Javascript
小夏不饿头像 小夏不饿 
function FindKthToTail( pHead ,  k ) {
    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-10-01 15:13:23 回复(0)
Javascript
Veagau头像 Veagau 
function FindKthToTail( pHead ,  k ) {
    // write code here
    let pA = pHead;
    let pB = pHead;
    let count = 0;
    if(pHead===null){
        return ListNode(null);
    }
    while(pA!==null && k>0){
        pA = pA.next;
        k--;
    }
    
    if(k>0){
        return ListNode(null);
    }
    while(pA!==null){
        pA = pA.next;
        pB = pB.next;
    }
    return pB;

}

发表于 2021-09-18 16:25:32 回复(0)
Javascript
牛客246205877号头像 牛客246205877号 
function ListNode(x){
  this.val = x;
  this.next = null;
 }

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
function FindKthToTail( pHead ,  k ) {
    let arr = []
    while(pHead){
        arr.push(pHead);
        pHead = pHead.next
    }
    if(arr.length >= k && k !== 0){
       let beforeNode = arr.pop()
        while(--k > 0){
            let temp = arr.pop();
            temp.next = beforeNode;
            beforeNode = temp
        }
        return beforeNode
    }else{
        return null
    }
    
}
module.exports = {
    FindKthToTail : FindKthToTail
};

发表于 2021-09-08 14:50:54 回复(0)
Javascript
牛客822067661号头像 牛客822067661号 
function FindKthToTail( pHead ,  k ) {
    let len = 0,p=pHead;
    while(pHead != null){
        len++;
        pHead=pHead.next;
    }
    if(len < k){
        return null
    }else{
       for(let i=0;i<len-k;i++){
           p = p.next
       }
        return p
    }
}

发表于 2021-08-09 21:04:59 回复(0)
Javascript
木琴要加油头像 木琴要加油 
 

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(!pHead || k <= 0) {
        return null;
    }
    let len = 0;
    let p = pHead;
    while(p) {
        len++;
        p = p.next
    }
    let a = 0;
    while(pHead) {
        if(a === (len-k)){
            return pHead;
            break;
        }
        a++;
        pHead = pHead.next;
    }
}
module.exports = {
    FindKthToTail : FindKthToTail
};
发表于 2021-08-05 14:26:58 回复(0)
Javascript
webchang头像 webchang
使用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)
JavaScript
NPC201904301802722头像 NPC201904301802722 
function FindKthToTail( pHead ,  k ) {
    if(!pHead){
        return null
    }
    // write code here
    let res=fn(pHead,k)
    if(typeof res==="number"){
        return null
    }
    return res
}
function fn( pHead ,  k ){
    if(!pHead.next){
        if(k===1){
            return pHead
        }else{
            return 1
        }
    }
    
    let res=fn(pHead.next,k)
    if(typeof res==="number"){
        res+=1
        if(res===k){
            return pHead
        }else{
            return res
        }
    }else{
        return res
    }
}
递归，从后往前数
编辑于 2021-06-16 20:01:29 回复(0)
JavaScript
别卷啦！头像 别卷啦！
快慢指针指向头部，快指针先走n-1，然后再同时走，快指针走到末尾的时候，慢指针指向倒数第k个节点 
function FindKthToTail( pHead ,  k ) {
    // write code here
    let fast = pHead, slow = pHead, i = 0
    
    while(k > 0){
        if(fast){
            fast = fast.next
            k--
        }else{
            return null
        }
    }
    while(fast){
        fast = fast.next
        slow = slow.next
    }
    return  slow
}


编辑于 2021-06-15 23:14:32 回复(0)
JavaScript
一直赢好无奈头像 一直赢好无奈 
function FindKthToTail( pHead ,  k ) {
    if(!pHead) return;
    let cur = pHead , slow = pHead;
    do{ if(k-- <= 0) slow = slow.next; } while(cur = cur.next);
    return k > 0 ? null : slow;
}

发表于 2021-04-27 20:53:20 回复(0)
JavaScript
splwany头像 splwany 
function FindKthToTail( pHead ,  k ) {
    if (!pHead || k === 0) return null;
    let right = pHead;
    for (let i = 0; i < k; i++) {
        if (!right) return null;
        right = right.next;
    }
    while (right) {
        right = right.next;
        pHead = pHead.next;
    }
    return pHead;
}

发表于 2021-04-02 16:43:52 回复(0)
JavaScript
咦我的offer呢头像 咦我的offer呢 
function FindKthToTail( pHead ,  k ) {
    if (!pHead) return null;
    let fast = pHead;
    let slow = pHead;

    while (k-- && fast) {
        fast = fast.next;
    }
    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }
    // 链表长度小于k时返回空
    return k ? slow : null;
}

发表于 2021-04-01 10:01:20 回复(0)
JavaScript
球球来一个offer吧头像 球球来一个offer吧
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)
提交观点

问题信息

链表
上传者：灵溪吴彦祖
难度：
21条回答 5814浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号