LeetCode 面试题 02.02. 返回倒数第 k 个节点

àì夳堔傛蜴生んèń 2022-12-06 12:32 105阅读 0赞

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

法一：双指针法：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        int kthToLast(ListNode* head, int k) { 
            ListNode *left = head, *right = head;
    
            for (int i = 1; i < k; ++i) { 
                right = right->next;
            }
    
            while (right->next != nullptr) { 
                left = left->next;
                right = right->next;
            }
    
            return left->val;
        }
    };

此方法时间复杂度为O（n+k），空间复杂度为O（1），n为链表长度。

法二：使用辅助栈：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        int kthToLast(ListNode* head, int k) { 
            stack<int> s;
            while (head != nullptr) { 
                s.push(head->val);
                head = head->next;
            }
    
            for ( ; k > 1; --k) { 
                s.pop();
            }
    
            return s.top();
        }
    };

此方法时间复杂度为O（n+k），空间复杂度为O（n），n为链表长度，仅作思路扩充，遇到要找倒数第几个的问题时，可使用栈。

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode：面试题 02.02. Kth Node From End of List LCCI 返回倒数第 k 个节点（C语言）

题目描述：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。注意：本题相对原题稍作改动示例：输入： 1->2->3->4->5 和 k = 2

小咪咪/ 2023年02月28日 04:27/ 0 赞/ 80 阅读

相关力扣刷题11--返回倒数第k个节点

题目实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。注意：本题相对原题稍作改动示例：输入： 1->2->3->4->5

绝地灬酷狼/ 2023年02月26日 13:26/ 0 赞/ 10 阅读

相关程序员面试金典-面试题02.02-返回倒数第 k 个节点

程序员面试金典-面试题02.02-返回倒数第 k 个节点这题同样是双指针，类似的有[程序员面试金典-面试题02.01-移除重复节点][-_02.01-] 实现

矫情吗；*/ 2022年12月27日 12:34/ 0 赞/ 164 阅读

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

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

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

相关 LeetCode 面试题 02.02. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。法一：双指针法： / Definition for singly-linked list. s

àì夳堔傛蜴生んèń/ 2022年12月06日 12:32/ 0 赞/ 106 阅读

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

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

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

相关面试题 02.02. 返回倒数第 k 个节点

[面试题 02.02. 返回倒数第 k 个节点][02.02. _ k] [https://leetcode-cn.com/problems/kth-node-from-en

绝地灬酷狼/ 2022年11月26日 01:52/ 0 赞/ 110 阅读

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

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

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

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

> 代码的鲁棒性 > 鲁棒性： > 指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理 > 提高鲁棒性方法：防御性编程 > 防御性编程：

谁践踏了优雅/ 2022年03月25日 01:52/ 0 赞/ 123 阅读

相关 Leetcode之打印链接的倒数第K个节点

1 问题打印链表倒数第K个节点值。 2 代码实现 include<stdio.h>

「爱情、让人受尽委屈。」/ 2021年09月25日 04:34/ 0 赞/ 133 阅读