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

àì夳堔傛蜴生んèń 2022-12-06 12:32 193阅读 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 条评论，193人围观）

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

相关阅读

相关【剑指】倒数第k个节点

这题又要注意的地方： //双指针算法 public: ListNode FindKthToTail(ListNode pListHead, u

男娘i/ 2023年06月21日 03:49/ 0 赞/ 28 阅读

相关面试题22. 链表中倒数第k个节点

题目来源 [面试题22. 链表中倒数第k个节点][22. _k] [面试题 02.02. 返回倒数第 k 个节点 ][02.02. _ k _] 题目描述 !

野性酷女/ 2023年03月14日 13:24/ 0 赞/ 87 阅读

相关 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 赞/ 176 阅读

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

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

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

相关面试题22. 链表中倒数第k个节点

题目： [面试题22. 链表中倒数第k个节点][22. _k] [\[编程题\]链表中倒数第k个结点][k] ![在这里插入图片描述][watermark_typ

傷城~/ 2023年02月09日 05:23/ 0 赞/ 98 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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