Lintcode174-Remove Nth Node From End of List-Easy

174. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

Example

Example 1:
	Input: list = 1->2->3->4->5->null， n = 2
	Output: 1->2->3->5->null


Example 2:
	Input:  list = 5->4->3->2->1->null, n = 2
	Output: 5->4->3->1->null

Challenge

Can you do it without getting the length of the linked list?

Notice

The minimum number of nodes in list is n.

思路：

双指针法：定义一个快指针，一个慢指针，初始都指向第一个节点。快指针提前走n 步，然后快慢指针一起走，当快指针的下一个为空时，删除慢指针的下一个。（不能：快指针为空时，删除慢指针，因为是单项链表，无法使慢指针的前一个指向慢指针的后一个（单项链表不保存上一个节点的地址））

注意：

忘了 n--;  结果死循环的后果是，NullPointerException, quick指针走到最后了。

代码：

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        ListNode quick = head;
        ListNode slow = head;
        
        if (n <= 0) 
            return null;
            
        while (n != 0) {
            quick = quick.next;
            n--;
        }
        
        while (quick.next != null) {
            slow = slow.next;
            quick = quick.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

九章代码：

head （快指针）从第一个节点开始，所以 while (head != null) 。preDelete(慢指针) 从头节点开始。

这个思路，指针定义的更专业，要理解head 比preDelete多走一个节点。quick slow定义不太好。

public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode preDelete = dummy;
        for (int i = 0; i < n; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }
        while (head != null) {
            head = head.next;
            preDelete = preDelete.next;
        }
        preDelete.next = preDelete.next.next;
        return dummy.next;
    }