面试题：找出单链表倒数第N个元素

       第一种方法先求出元素个数，在遍历元素个数-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));
	}
}

 

 

评论

1 楼 cywhoyi 2015-01-18  

时间复杂度都是O（N），不管你是O（2N），都是O(N），我的想法是遍历后，放到stack，LIFO获取倒数的