第一种方法先求出元素个数,在遍历元素个数-n个,时间复杂度为:O(N+N-n)=O(2N-n)。
第二种设置俩个指针,第一个先走N步,第二个开始走。俩者速度一样,时间复杂度为O(N)。
代码如下:
package dataStructtion.linear; /** * 获取单链表倒数第N个元素 * @author xiucai */ public class SingleLinkedList_LastN { /** * 第一种方法先求出元素个数,在遍历元素个数-n个 * 时间复杂度为:O(N+N-n)=O(2N-n) * @param list * @param n * @return * @throws Exception */ public static<T> T getLastN1(SingleLinkedList<T> list,int n) throws Exception{ int count=0; Node<T> node=list.head; while(node.next!=null){ count++; node=node.next; } if(count<n) throw new Exception("单链表元素个数小于 "+n+" !"); node=list.head; for(int i=0;i<count-n;i++){ node=node.next; } return (T)node.data; } /** * 设置俩个指针,第一个先走N步,第二个开始走。俩者速度一样 * 时间复杂度为O(N) * @param list * @param n * @return * @throws Exception */ public static<T> T getLastN2(SingleLinkedList<T> list,int n) throws Exception{ //fastN先走N步,slowN等fastN走N步后在开始走 Node<T> fastN=list.head,slowN=list.head; for(int i=0;i<n;i++){ if(fastN.next==null){ throw new Exception("单链表元素个数小于 "+n+" !"); /*try { } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); }*/ } fastN=fastN.next; } while(fastN.next!=null){ fastN=fastN.next; slowN=slowN.next; } return (T)slowN.data; } //测试方法 public static void main(String[] args) throws Exception { SingleLinkedList<String> list=new SingleLinkedList<String>(); for(int i=1;i<=100;i++){ list.append("第"+i+"个"); } System.out.println(getLastN2(list, 1000)); } }
相关推荐
很多大公司的面试题,查找单链表倒数第N个节点
09_拼多多面试真题:如何找出连续出现N次的内容?
算法大全面试题数据结构单链表的13道面试题含代码 1.单链表反转 2.找出单链表的倒数第四个元素 3.找出单链表的中间元素 4...
以后会慢慢把Java相关的面试题、计算机网络等都加进来,其实这不仅仅是一份面试题,更是一份面试参考,让你熟悉面试题各种提问情况,当然,项目部分,就只能看自己了,毕竟每个人简历、实习、项目等都不一样。面试题...
前端面试题: 精选Vue面试题及答案.pdf
经典面试题: 2021Vue经典面试题总结(含答案).pdf
python笔记50-面试题:交换圣诞节礼物全文共5页,当前为第1页。python笔记50-面试题:交换圣诞节礼物全文共5页,当前为第1页。python笔记50-面试题:交换圣诞节礼物 python笔记50-面试题:交换圣诞节礼物全文共5页,...
找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级...
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
以后会慢慢把Java相关的面试题、计算机网络等都加进来,其实这不仅仅是一份面试题,更是一份面试参考,让你熟悉面试题各种提问情况,当然,项目部分,就只能看自己了,毕竟每个人简历、实习、项目等都不一样。面试题...
医疗卫生面试真题:卫生类典型面试题汇总及答案.pdf
2021最新大厂AI面试题:Q3版107题(含答案及解析).pdf
2021最新大厂AI面试题:107题(含答案及解析).pdf
⾯试题: ⾯试题:robotframework题 题 根据我之前总结的robotframework笔记,相信这些题不在话下,否则的话,只能再去回顾⼀遍啦! 01: :RF⽀持的四种表? ⽀持的四种表? Setting,Variable,Testcase,keywords...
2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级...
面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速...
最新面试题:vue-面试题.pdf
经典面试题:最长公共子序列.html