与倒数第N个节点相关的题目

基础链表构造：

public class ListNode {
	public int val;
	public ListNode next;

	public ListNode(int val, ListNode next) {
		super();
		this.val = val;
		this.next = next;
	}

	public ListNode(int val) {
		super();
		this.val = val;
	}

	public static ListNode arrayToList(int[] arr) {
		ListNode head = new ListNode(0);
		ListNode p = head;
		for(int value : arr){
			p.next = new ListNode(value);
			p = p.next;
		}
		return head.next;
	}
	
	public static void printList(ListNode head){
		ListNode p = head;
		while(p != null){
			System.out.print(p.val + " ");
			p = p.next;
		}
		System.out.println();
	}
}

相关面试题：

public class 倒数第N个节点 {
	public static void main(String[] args){
		int[] array = {1,2,3,4,5,5,5,6,7,8};
		ListNode head = ListNode.arrayToList(array);
		ListNode.printList(head);
		
		int n = lengthOfList(head);
		System.out.println(n);
		
		int x = 3;
		System.out.println(getLastNth(head,x).val);//查询倒数第N个节点
		int d = 3;
		
		deleteLastNth(head,d);					//删除倒数第N个节点
		ListNode.printList(head);
		
		removeElements(head,5);
		ListNode.printList(head);				//查询节点并删除
		
	}
	
	/**
	 * 删除掉指定的某个元素
	 * @param head
	 * @param i
	 */
	private static void removeElements(ListNode head, int i) {
		ListNode pre = head;   //定义双指针，目的是找到将要删除节点的前一个节点，以便执行删除操作
		ListNode p = head;
		while(p != null){
			if(p.val == i){
				pre.next = p.next;
				p = p.next;
			}else{
				pre = p;
				p = p.next;
			}
		}
	}
/**
 * 删除倒数第N个节点
 * @param head
 * @param d
 */
	private static void deleteLastNth(ListNode head, int d) {
		ListNode p = head;
		ListNode pre = head;
		for(int i = 0; i < d+1; i++){	//多加1，就是返回要删除节点的前一个节点的位置
			p = p.next;
		}
		while(p != null){				//多加1，就是返回要删除节点的前一个节点的位置
			p = p.next;
			pre = pre.next;
		}
		pre.next = pre.next.next;
	}
/**
 * 查找倒数第N个节点
 * @param head
 * @param x
 * @return
 */
	private static ListNode getLastNth(ListNode head,int x) {
		ListNode p = head;
		ListNode pre = head;
		for(int i = 0; i < x; i++){
			p = p.next;
		}
		while(p != null){
			p = p.next;
			pre = pre.next;
		}
		return pre;
	}
/**
 * 链表长度
 * @param head
 * @return
 */
	private static int lengthOfList(ListNode head) {
		int count = 0;
		ListNode p = head;
		while(p != null){
			count++;
			p = p.next;
		}
		return count;
	}
}