牛客网高频算法题系列-BM8-链表中倒数最后k个结点
2022/6/2 1:23:21
本文主要是介绍牛客网高频算法题系列-BM8-链表中倒数最后k个结点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
牛客网高频算法题系列-BM8-链表中倒数最后k个结点
题目描述
描述:输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。如果该链表长度小于k,请返回一个长度为 0 的链表。
原题目见:BM8 链表中倒数最后k个结点
解法一:双指针法
首先,考虑两种特殊情况:
- 如果原链表为空,直接返回null。
- 如果k不是正数,直接返回null。
否则,使用双指针求解,求解过程如下:
- 首先,遍历链表,将fast结点指向第k个结点;
- 如果遍历完后fast为null,说明链表长度小于k,不存在倒数第k个结点,直接返回null;
- 否则,快慢指针一起移动,直到fast移动到最后一个结点,此时,slow即为倒数第k个结点,返回之。
代码
public class Bm008 { /** * 链表中倒数最后k个结点 * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ public static ListNode findKthToTail(ListNode pHead, int k) { // 如果原链表为空,直接返回null if (pHead == null) { return null; } // 如果k不是正数,直接返回null if (k <= 0) { return null; } ListNode fast = pHead; // 将fast结点指向第k个结点 for (int i = 0; i < k - 1 && fast != null; i++) { fast = fast.next; } // 如果fast为null,说明链表长度小于k,不存在倒数第k个结点,直接返回null if (fast == null) { return null; } ListNode slow = pHead; // 快慢指针一起移动,直到fast移动到最后一个结点,此时,slow即为倒数第k个结点 while (fast.next != null) { slow = slow.next; fast = fast.next; } return slow; } public static void main(String[] args) { ListNode pHead = ListNode.testCase2(); System.out.println("原链表为"); ListNode.print(pHead); int k = 2; System.out.println("链表中的倒数第" + k + "个结点为:"); System.out.println(findKthToTail(pHead, k)); } }
\(1.01^{365} ≈ 37.7834343329\)
\(0.99^{365} ≈ 0.02551796445\)
相信坚持的力量!
这篇关于牛客网高频算法题系列-BM8-链表中倒数最后k个结点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)