链表中倒数第k个节点

末蓝、 2022-11-22 00:23 194阅读 0赞

# 链表中倒数第k个节点 #

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
    
    返回链表 4->5.

# 代码与思路 #

计算长度，找到要删除节点的前一个节点

class Solution { 
    public:
        ListNode* getKthFromEnd(ListNode* head, int k) { 
            ListNode* p = head;
            int len = 0;
            while(p!=NULL){ 
                len++;
                p = p->next;
            }
            int num = len - k;
            p = head;
            while(num>0){ 
                p = p->next;
                num--;
            }
            return p;
        }
    };

# 双指针，一次遍历 #

第一个指针先前进K步，然后两个指针一起前进。

class Solution { 
    public:
        ListNode* getKthFromEnd(ListNode* head, int k) { 
            ListNode* fast = head;
            ListNode* slow = head;
            while(k--) { 
                fast = fast->next;
            }
            while(fast) { 
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关查找链表中倒数第k个节点

问题：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、

怼烎@/ 2022年12月19日 00:54/ 0 赞/ 186 阅读

相关返回链表中倒数第k个节点

思路：定义fast 和 slow ，先让fast走k-1步，然后再让slow和fast同时走1步，最后得到的slow就是所求的值 ![在这里插入图片描述][waterm

灰太狼/ 2022年12月18日 02:58/ 0 赞/ 182 阅读

相关链表中倒数第k个节点

[https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&rp=1&ru=%2Ft

逃离我推掉我的手/ 2022年11月30日 04:17/ 0 赞/ 197 阅读

相关链表中倒数第 k 个节点

链表中倒数第 k 个节点 1、参考资料 https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kg

港控/mmm°/ 2022年11月29日 03:09/ 0 赞/ 198 阅读

相关链表中倒数第k个节点

链表中倒数第k个节点输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节

末蓝、/ 2022年11月22日 00:23/ 0 赞/ 195 阅读

相关 15_链表中倒数第k个节点

> 题目：输入一个链表，输出该链表中倒数第k个结点。 > 本题从1开始计数，即链表的尾结点是倒数第1个结点。 > 例如一个链表有6个结点，从头结点开始它们的值依次是1、

分手后的思念是犯贱/ 2022年06月08日 09:55/ 0 赞/ 189 阅读

相关链表中倒数第k个节点

package cn.com.jianzhioffer; import java.util.List; public

╰+攻爆jí腚メ/ 2022年05月24日 04:59/ 0 赞/ 185 阅读

相关链表问题_链表中倒数第K个节点

题目：输入一个链表，输出该链表中倒数第k个节点。尾节点为倒数第一个节点。分析：可以采用两个指针，记为start和end，先让end在链表上走k-1步，然后两个节点同时开始

水深无声/ 2022年05月21日 01:41/ 0 赞/ 190 阅读

相关【Java】链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。 package 牛客; public class ListNode { in

- 日理万妓/ 2022年01月23日 05:21/ 0 赞/ 347 阅读

相关链表之链表中倒数第k个节点

public class Solution { public ListNode FindKthToTail(ListNode head,int k) {

小鱼儿/ 2021年09月18日 04:54/ 0 赞/ 328 阅读