【刷穿 LeetCode】剑指 Offer 22. 链表中倒数第k个节点 :「栈/队列」&「差值法」&「快慢指针」

简介: 【刷穿 LeetCode】剑指 Offer 22. 链表中倒数第k个节点 :「栈/队列」&「差值法」&「快慢指针」

网络异常,图片无法展示
|

题目描述



这是 LeetCode 上的 剑指 Offer 22. 链表中倒数第k个节点 ,难度为 简单


Tag : 「链表」、「栈」、「队列」、「快慢指针」


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


例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。


示例:


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


栈/队列 解法



一个使用额外空间的解法是利用栈(队列),将所有的节点压入占中栈(队列)中,令当前栈(队列)容量为 cntcnt


然后从栈顶(队列头)弹出 kk 个(cnt - k + 1cntk+1 个)元素,最后一个出栈(出队列)的元素即是答案。


网络异常,图片无法展示
|


代码(栈):


class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while (head != null) {
            d.addLast(head);
            head = head.next;
        }
        ListNode ans = null;
        while (k-- > 0) ans = d.pollLast();
        return ans;
    }
}
复制代码


代码(队列):


class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while (head != null) {
            d.addLast(head);
            head = head.next;
        }
        k = d.size() - k + 1;
        ListNode ans = null;
        while (k-- > 0) ans = d.pollFirst();
        return ans;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


差值法



我们可以先对链表进行一次完整遍历,拿到总长度 cntcnt,最后由 cnt - kcntk 即是倒数第 kk 个节点距离 headhead 节点的距离。


网络异常,图片无法展示
|


代码:


class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int cnt = 0;
        ListNode tmp = head;
        while (tmp != null && ++cnt > 0) tmp = tmp.next;
        cnt -= k;
        while (cnt-- > 0) head = head.next;
        return head; 
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)


快慢指针



事实上,我们还可以使用「快慢指针」进行求解。


起始先让快指针 fast 先走 kk 步,此时 fastslow 之间距离为 kk,之后让 fastslow 指针一起走(始终维持相对距离为 kk),当 fast 到达链表尾部,slow 即停在倒数第 kk 个节点处。


网络异常,图片无法展示
|


代码:


class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.剑指 Offer 22. 链表中倒数第k个节点 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
143 6
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
149 4
|
12月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
131 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
12月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
130 0
|
12月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
76 0
|
12月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
79 0
|
12月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
160 0
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
152 5
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
111 4