力扣 - 剑指 Offer 22. 链表中倒数第k个节点
2021/11/19 6:40:22
本文主要是介绍力扣 - 剑指 Offer 22. 链表中倒数第k个节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 22. 链表中倒数第k个节点
思路1(栈)
- 既然要倒数第k个节点,那我们直接把所有节点放到栈(先进后出)里面,然后pop弹出k个元素就可以了
代码
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { LinkedList<ListNode> stack = new LinkedList<>(); // 把整个链表入栈 while (head != null) { stack.push(head); head = head.next; } // 先将前n-1个元素出栈 for (int i = 1; i < k; i++) { stack.pop(); } // 此时位于栈顶的就是倒数第k个元素啦 return stack.pop(); } }1
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(N)\),使用栈的额外空间要花掉\(O(N)\)
思路2(递归+回溯)
- 和使用栈的思想差不多。。
- 先递归到链表末尾,然后依次回溯,回溯k次的时候就得到我们需要的节点了
代码
class Solution { ListNode res; // 代表当前处于倒数第几个节点 int cur = 0; public ListNode getKthFromEnd(ListNode head, int k) { dfs(head, k); return res; } public void dfs(ListNode node, int k) { // 先递归到末尾 if (node == null) { return; } dfs(node.next, k); // 倒数第cur个节点 cur++; // 等于k代表找到了 if (cur == k) { res = node; } } }
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(N)\),需要递归整个链表
思路3(双指针)
- 定义
fast
快指针和slow
慢指针两个指针:让快指针fast
先走k
步,然后再让两个指针同时移动,等快指针fast
走道链表末尾时候(为null
),此时慢指针slow
所指向的节点就是倒数第k
个节点
代码
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; // 让快指针先走k步,和慢指针相差k个距离 for (int i = k; i > 0; i--) { fast = fast.next; } // 此时让慢指针和快指针同时走,知道快指针到达链表末尾为null时,慢指针就在倒数第k个位置上了 while (fast != null) { fast = fast.next; slow = slow.next; } // 直接返回慢指针即为答案 return slow; } }
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(1)\)
思路4(差值法)
- 因为要求的是倒数第k个节点,那如果我们知道了链表的总长度,那么这个节点在链表中的顺序位置也就知道了
- 先计算出链表的总长度,则可以得出:
倒数第k个节点
等于链表总长度-k+1
。但是在题目中我们已经指向了链表的第一个节点,所以只需要再走n-k
个节点即可到达倒数第k个节点
代码
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { int length = 0; ListNode p = head; // 先获取链表的总长度 while (p != null) { p = p.next; length++; } // 其实倒数第k个的位置就相当于 length-k // 然后我们从链表头部开始遍历 length-k 个节点,此时所在的节点位置就是答案了 k = length - k; for (int i = k; i > 0; i--) { head = head.next; } return head; } }
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(1)\)
这篇关于力扣 - 剑指 Offer 22. 链表中倒数第k个节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt