腾讯的面试题：找出未知单链表中点元素_JAVA_编程开发_程序员俱乐部

? ? ? ?腾讯的面试题：找出未知单链表中点元素？

? ? ? ?俩种方法：

? ? ? ? ? ? ? ? ? ? ? ? 第一种：全部遍历算出总长度为length；再遍历length/2个元素。时间复杂度为O(3N/2)

? ? ? ? ? ? ? ? ? ? ? ? 第二种：设置快慢指针。search速度为2，middle速度为1。当search完一遍时，middle正好 ? ? ? ? ? ? ? ? ? ?为中点元素。此时时间复杂度为O(N)。

? ? ? ? ? ? ? ? ? ? ? ? 其实还有第三种：若在单链表中设置len属性记录单链表长度，那么直接遍历N/2即可时间复杂 ? ? ? ? ? ? ? ? ?度为O(N/2)。

? ? ? ?代码如下：

? ? ?

class="java">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));
	}
}

?