腾讯的面试题:找出未知单链表中点元素?
俩种方法:
第一种:全部遍历算出总长度为length;再遍历length/2个元素。时间复杂度为O(3N/2)
第二种:设置快慢指针。search速度为2,middle速度为1。当search完一遍时,middle正好 为中点元素。此时时间复杂度为O(N)。
其实还有第三种:若在单链表中设置len属性记录单链表长度,那么直接遍历N/2即可时间复杂 度为O(N/2)。
代码如下:
package dataStructtion.linear; /** * 找出未知单链表中点元素 * @author xiucai */ public class MiddleSingleLinked{ /** * 先求长度n * 再求n/2位置的元素 * 时间复杂度为:O(n+n/2)=O(3N/2) * @param list * @return */ public static<T> T getMiddle1(SingleLinkedList<T> list){ int count=0; Node<T> node=list.head; while(node.next!=null){ count++; node=node.next; } node=list.head; int middle=count%2==0?count/2:1+count/2; for(int i=0;i<middle;i++){ node=node.next; } return (T)node.data; } /** * 快慢指针,时间复杂度为O(N/2+N/2)=O(N) * @param list * @return */ public static<T> T getMiddle2(SingleLinkedList<T> list){ Node<T> middle=list.head;//记录中点数,速度为1 Node<T> search=list.head;//速度为2 while(search.next!=null){ //偶数情况下 if(search.next.next!=null){ search=search.next.next; middle=middle.next; } //奇数情况下 else { search=search.next; middle=middle.next; } } return (T)middle.data; } /** * 若在单链表中设置len属性记录单链表长度,那么直接遍历N/2即可 * 时间复杂度为O(N/2) * @param list * @return */ public static<T> T getMiddle3(SingleLinkedList<T> list){ int len=list.length(); int middle=len%2==0?len/2:1+len/2; Node<T> node=list.head; for(int i=0;i<middle;i++){ node=node.next; } return (T)node.data; } /** * 测试算法 * @param args */ public static void main(String[] args) { SingleLinkedList<String> list=new SingleLinkedList<String>(); list.append("a"); list.append("b"); list.append("c"); list.append("d"); System.out.println(list); System.out.println(getMiddle2(list)); list.append("e"); System.out.println(list); System.out.println(getMiddle2(list)); } }
相关推荐
大数据面试题V3.0完成了。共523道题,679页,46w+字,来源于牛客870+篇面经。 主要分为以下几部分: Hadoop面试题:100道 Zookeeper面试题:21道 Hive面试题:47道 Flume面试题:11道 Kafka面试题:59到 HBase面试题...
前端面试题: 精选Vue面试题及答案.pdf
经典面试题: 2021Vue经典面试题总结(含答案).pdf
算法大全面试题数据结构单链表的13道面试题含代码 1.单链表反转 2.找出单链表的倒数第四个元素 3.找出单链表的中间元素 4...
医疗卫生面试真题:卫生类典型面试题汇总及答案.pdf
2021最新大厂AI面试题:Q3版107题(含答案及解析).pdf
大数据面试题V3.0完成了。共523道题,679页,46w+字,来源于牛客870+篇面经。 主要分为以下几部分: Hadoop面试题:100道 Zookeeper面试题:21道 Hive面试题:47道 Flume面试题:11道 Kafka面试题:59到 HBase面试题...
2021最新大厂AI面试题:107题(含答案及解析).pdf
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
最新面试题:vue-面试题.pdf
⾯试题: ⾯试题:robotframework题 题 根据我之前总结的robotframework笔记,相信这些题不在话下,否则的话,只能再去回顾⼀遍啦! 01: :RF⽀持的四种表? ⽀持的四种表? Setting,Variable,Testcase,keywords...
经典面试题:最长公共子序列.html
vue面试题: 前端面试题库
医疗卫生面试真题:卫生类典型面试题汇总.docx
Vue面试题:.txt
文章目录求单链表中有效节点的个数查找单链表中倒数第k个节点【新浪面试题】单链表的反转【腾讯面试题】从尾到头打印单链表【百度面试题,要求方式1:反向遍历。方式2:Stack栈】 单链表的常见面试题有如下: 1.求...
BAT及各大互联网公司2014前端笔试面试题:HTML