JZ14 链表中倒数最后k个节点
2021/7/6 23:07:59
本文主要是介绍JZ14 链表中倒数最后k个节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
描述
输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
示例1
输入:{1,2,3,4,5},1
返回值:{5}
1.遍历两次,第一次记个数,第二次找倒数
package com.LeetCodeProblem.JZ; import java.util.*; public class JZ14 { public ListNode FindKthToTail (ListNode pHead, int k) { if(k<=0||pHead==null) return null;// if(k<=0||pHead.equal(null)) return null;不行 int count=0; ListNode temp=pHead; while (temp!=null){ count++; temp=temp.next; } if(count<k) return null; temp=pHead; for (int i = 0; i < count - k; i++) { temp=temp.next; } return temp; } public class ListNode { int val; ListNode next = null; public ListNode(int val) { this.val = val; } } }
2.快慢指针
思路:
使用快慢指针
先让快指针走k个,然后快慢指针一起走
当快指针为null时,慢指针就为所求
如何判断k是否合法呢?
在快指针走k个后,如果k大于链表长度
就会在循环里为null,这时候就说明k太大而不合法
而当快指针走完后,循环结束
正好为null,则此时结果正好是pHead。
public ListNode FindKthToTail (ListNode pHead, int k) { if(pHead == null || k <= 0) return null; //slow为慢指针,p为快指针 ListNode p = pHead,slow = pHead; for(int i = 0;i < k;i++){ //循环里p如果为null,说明k已经超出链表长度范围 if(p == null) return null; p = p.next; } //p如果正好为null,则所求为倒数第链表长度个,为pHead if(p == null) return pHead; //快慢指针同时往右移 while(p != null){ p = p.next; slow = slow.next; } return slow; }
这篇关于JZ14 链表中倒数最后k个节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现