LeetCode: Remove Nth Node From End of List

Given a linked list, remove the n^th 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.

---

We can use two pointers, one is fast and one is slow. Make the fast node move first n-1 steps, then start moving two nodes together.

C++ Code:

/*
 * func: remove_nth_from_end
 * goal: remove the nth node from the end the list in one pass
 * @param head: the head of the list
 * @param n: the nth
 * return: the head of the linked list
 */
/*
 * use two pointers, one slow pointer and one fast pointer, make the fast
 * pointer ahead of slow pointer n steps
 */
ListNode* remove_nth_from_end(ListNode *head, int n){
    if(head == nullptr || n < 1){
        return head;
    }
    ListNode *fast = head;
    ListNode *slow = head;
    //Record the previous node of slow
    ListNode *pre_slow = nullptr;
    int counter = 1;
    
    //Move fast ahead
    while(fast->next != nullptr && counter < n){
        fast = fast->next;
        ++counter;
    }
    //If there are not enough nodes
    if(counter < n){
        return head;
    }
    
    //Move all nodes
    while(fast->next != nullptr){
        fast = fast->next;
        pre_slow = slow;
        slow = slow->next;
        
    }
    
    //Cancatenate nodes
    if(pre_slow != nullptr){
        //Not head node removed
        pre_slow->next = slow->next;
    }else{
        head = head->next;
    }
    
    return head;
}

Python Code:

# func: remove the nth node from end of the list
# @param head: head node of the list
# @param n: input number n
# @return: the head node
def remove_nth_from_end(head, n):
    if not head or n < 1:
        return head
    else:
        #Fast node to move first
        fast = head
        #Slow node to move later
        slow = head
        #node ahead of slow node
        pre_slow = None
        counter = 1

        #Start moving fast node
        while fast.next is not None and counter < n:
            fast = fast.next
            counter += 1

        #Check if there are enough nodes
        if counter < n:
            return head

        #Move all nodes forward
        while fast.next is not None:
            fast = fast.next
            pre_slow = slow
            slow = slow.next

        #Remove node
        #If head node is removed
        if pre_slow is None:
            head = head.next
        else:
            pre_slow.next = slow.next

        return head