Leetcode Study Day 29

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.

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

My solution

My solution is firstly iterate the list to get the length of the list. Then we can calculate the index of the node we want to remove. Then we iterate the list again to remove the node.

/**
 * 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) {
        ListNode* current = head;
        int count = 0;
        while (current){
            current = current->next;
            count += 1;
        }
        if (count == n)
            return head -> next;
        else if (count < n) return NULL;
        current = head;
        for (int i = 1; i < count - n; i++){
            current = current -> next;
        }
        if (current -> next)
            current -> next = current -> next -> next;
        else
            current -> next = NULL;
        return head;
    }
};

We can also use two pointers to solve this question. To be specific, we can create one pointer called fast and one pointer called slow. The fast pointer will move n steps first. Then the slow pointer will move with the fast pointer. When the fast pointer reaches the end of the list, the slow pointer will be at the node we want to remove.