【算法】删除链表的倒数第N个节点19

leetcode_删除链表的倒数第N个节点19

import java.util.Scanner;
//删除链表的倒数第N个节点19
public class RemoveNthNodeFromEndOfList19 {
	public static void main(String[] args){
		ListNode head = initLinkedList(new int[]{1,2,3,4,5});
		printLinkedList(head);
		System.out.print("请选择删除倒数第几个节点：");
		Scanner input = new Scanner(System.in);
		head = new Solution().removeNthFromEnd(head,input.nextInt());
		printLinkedList(head);
	}

	public static ListNode initLinkedList(int[] nums){
    	ListNode head = new ListNode(nums[0]);
    	ListNode cur = head,node;
    	for(int i = 1; i < nums.length; i++){
    		node = new ListNode(nums[i]);
    		cur.next = node;
    		cur = node;
    	}
    	return head;
    }
    public static void printLinkedList(ListNode head){
    	System.out.println();
    	ListNode cur = head;
    	while(cur != null){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }

}



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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    	if (head == null || n <= 0 || n > linkedListLength(head)) {
    		return null;
    	}
    	ListNode dummy = new ListNode(-1,head);
    	ListNode fast = dummy;
    	ListNode slow = dummy;

    	//fast 先走 n 步
    	for (int i = 0; i < n ; i++) {
    		fast = fast.next;
    	}
    	while(fast.next != null){
    		fast = fast.next;
    		slow = slow.next;
    	}
    	//slow 就是删除节点前一个
    	slow.next = slow.next.next;
    	return dummy.next;
    }

    public int linkedListLength(ListNode head){
    	if (head == null) {
    		return 0;
    	}
    	ListNode cur = head;
    	int count = 0;
    	do{
    		cur = cur.next;
    		count++;
    	}while(cur != null);
    	return count;
    }
}