Remove Nth Node From End of List

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.

思路

利用slow, fast双指针。首先fast先走n步，让slow和fast的距离为n，如果fast跑到最后为null的时候，slow正好是要删除的节点，因为这里要删除节点，所以让fast.next == null的时候，slow正好是要删除的节点的前一个节点，这时让slow.next = slow.next.next。这里要注意的是如果正好要删除的点是head，那么就没有一个pre的节点，这时要让head = head.next。

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    //corner case
    if(head == null || head.next == null) return null;
    ListNode fast = head, slow = head;
    //keep distance n from slow to fast
    for(int i = 0; i < n; i++){
        fast = fast.next;
        //when the deleteNode is the head node, so we can't keep the pre node, we need to have a new head
        if(fast == null){
            head = head.next;
            return head;
        }
    }
    //we need to find the preDeleteNode, so we need fast to stop at the last node
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return head;
}