寻找链表的倒数第N个节点

package 链表中;

public class NthNodeFromEndOfList {
	/**
	 * 获取链表的长度
	 */
	public static int lengthOfList(ListNode head) {
		int m = 0;
		ListNode p = head;
		while(p != null) {
			m++;
			p = p.next;
		}
		return m;
	}
	
	/*
	 * 方法一：遍历两遍链表
	 */
	public static ListNode find01(ListNode head,int n) {
		ListNode p = head;
		int m = lengthOfList(head);
		for (int i = 0; i < m-n; i++) {
			p = p.next;
		}
		return p;
	}
	
	/**
	 * 方法二：只遍历一遍链表，允许多指针
	 * 思路：定义指针p1,p2
	 * 	   指针p2往后移动N位
	 *   同时将p1,p2往后移动，直到p2遇到null
	 * @param args
	 */
	public static ListNode find02(ListNode head, int n) {
		ListNode p1 = head;
		ListNode p2 = head;
		for (int i = 0; i < n; i++) {
			p2 = p2.next;
		}
		while (p2 != null) {
			p2 = p2.next;
			p1 = p1.next;
		}
		return p1;
	}
	
	public static void main(String[] args) {
		int[] array = {1,2,3,4,5,6};
		ListNode head01 = ListNode.arrayToList(array);
		System.out.print("单指针，多遍历： ");
		System.out.println(find01(head01, 1));
		
		ListNode head02 = ListNode.arrayToList(array);
		System.out.print("多指针，单遍历： ");
		System.out.println(find02(head02, 3));
	}
}