[LeetCode Road] Remove Nth Node From End of List - Solution/C++

19. Remove Nth Node From End of List

Question:

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

Follow up: Could you do this in one pass?

Example:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Input: head = [1], n = 1
Output: []

Input: head = [1,2], n = 1
Output: [1]

Constaints:

The number of nodes in the list is sz.

01 <= sz <= 30

00 <= Node.val <= 100

01 <= n <= sz

Source code

Version 1

Idea:
This method uses fast & slow pointers. It is similar with 141. Linked List Cycle.

Fast pointer moves n steps first. It means the distance is n between fast pointer and slow pointer.

What the concept of the method?
When the fast pointer reaches to the end of the list, the slow points will stop at n^th from the end of the list. At the monent, the next node of slow pointer is the answer to remove it.

The demonstration is shown as below:

Time complexity: O(L)
Space complexity: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return head;
        
        ListNode dummy(0);
        ListNode* ptr = &dummy;
        ptr->next = head;
        
        auto fast = ptr;
        auto slow = ptr;
        
        while(fast->next){
            fast = fast->next;
            if(n-- <= 0){
                slow = slow->next;
            }
        }
        slow->next = slow->next->next;
        return dummy.next;
    }
};