Problem

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

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

思路一(Two-pass)

• 得出list的长度len
• 使用dummy node, 因为头指针可能改
• prev, curt node, 因为需要删除
• 找到第len - n个点, 删除

    ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode curt = head;
        while (curt != null) {
            len++;
            curt = curt.next;
        }

        if (n > len) return null;

        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;

        dummy.next = head;
        curt = head;

        for (int i = 1; i <= len - n; i++) {
            ListNode temp = curt.next;
            prev = curt;
            curt = temp;
        }

        prev.next = curt.next;

        return dummy.next;
    }

思路二(One-pass)

• fast node 和 slow node 保持n个node的距离
• fast 和 slow 起始是dummy node

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode start = new ListNode(0);
    start.next = head;
    ListNode slow = start, fast = start;

    //Move fast in front so that the gap between slow and fast becomes n
    for(int i=1; i<=n+1; i++)   {
        fast = fast.next;
    }
    //Move fast to the end, maintaining the gap
    while(fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    //Skip the desired node
    slow.next = slow.next.next;
    return start.next;
}