学步园

2.2 Implement an algorithm to find the nth to last element of a singly linked list.

两个指针间距n-1，后一个指针走到底时返回第一个指针即可，注意要检查cur是否为空，防止n过大。

package Question2_2;

public class Question2_2<AnyType>
{
	public static void main(String[] args)
	{
		Question2_2<Integer> q = new Question2_2<Integer>();
		
		q.AddToList(4);q.AddToList(5);q.AddToList(6);q.AddToList(7);
		q.AddToList(1);q.AddToList(0);q.AddToList(1);q.AddToList(8);
		q.AddToList(3);q.AddToList(2);q.AddToList(5);q.AddToList(4);
		q.PrintList();
		q.FindNthToLast(10).PrintNode();
	}
	
	
	private Node<AnyType> head;
	
	public Question2_2()
	{
		head = new Node<AnyType>(null, null);
	}
	
	public void AddToList(AnyType e)
	{
		Node<AnyType> temp = head;
		while (temp.next != null)
			temp = temp.next;
		temp.next = new Node<AnyType>(e, null);
	}
	
	public Node<AnyType> FindNthToLast(int n)
	{
		Node<AnyType> pre = head;
		Node<AnyType> cur = pre;
		
		for (int i = 0; i < n; i++)
		{
			if (cur == null)
				return null;
			cur = cur.next;
		}
			
		while (cur != null)
		{
			pre = pre.next;
			cur = cur.next;
		}
		
		return pre;
	}
	
	public void PrintList()
	{
		Node<AnyType> temp = head;
		while (temp.next != null)
		{
			temp = temp.next;
			System.out.print(temp.data + " ");
		}
		System.out.println();
	}
	
	private class Node<Type>
	{
		Node(Type d, Node<Type> n)
		{
			data = d;
			next = n;
		}
		
		void PrintNode()
		{
			System.out.println(data);
		}
		
		Type data;
		Node<Type> next;
	}
}