LeetCode 19. Remove Nth Node From End of List

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

Follow up: Could you do this in one pass?

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The number of nodes in the list is sz.

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

Solution 1:

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = 0;
        ListNode* head_copy = head;
        
        while (head_copy != nullptr) {
            head_copy = head_copy->next;
            len++;
        }
        
        if (n == len) {
            ListNode* new_head = head->next;
            delete head;
            return new_head;
        }
        
        head_copy = head;
        for (int i = 1; i < (len - n); i++) {
            head_copy = head_copy->next;
        }
        
        ListNode* to_delete = head_copy->next;
        head_copy->next = head_copy->next->next;
        delete to_delete;
        return head;
    }
};

Solution 2:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;
        ListNode* slow = head;

        for (int i = 0; i < n; i++) {
            fast = fast->next;
            if(fast == nullptr) {
                ListNode* new_head = head->next;
                delete head;
                return new_head;
            }
        }
        
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        ListNode* to_delete = slow->next;
        slow->next = slow->next->next;
        delete to_delete;
        return head;
    }
};