###### tags: `leetcode` `medium` `Linked List` `Two Pointers`
# [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

## Description

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

## Examples
### Example1


**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 \leq sz \leq 30$
- $0 \leq Node.val \leq 100$
- $1 \leq n \leq sz$

## Code

- Way 1

typedef struct ListNode ListNode;

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    int firstCheck = 1;
    ListNode *tmp = head, *preN = head, *last = NULL;

    // Find the distance with input number
    for (int i = 1; i < n; i++)
        tmp = tmp->next;

    // Move the whole set to the end
    for (; tmp->next != NULL ;) {
        tmp = tmp->next;
        last = preN;
        preN = preN->next;
        firstCheck = 0;
    }

    // If we wamt to remove the first number, we have to use NULL pointer.
    // Define a first number checker for checking
    if (firstCheck == 1) {
        tmp = head->next;
        free(head);
        return tmp;
    }

    // After we find pointers of the number we wanted and the previous number,
    // reconnect the linked list
    tmp = preN;
    last->next = preN->next;
    free(tmp);
    return head;
}

- Way 2

typedef struct ListNode ListNode;

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    int firstCheck = 1, index = 1;
    ListNode *tmp = head, *preN = head, *last = NULL;

    // Find the distance with input number
    for (; tmp->next ; index++)
        tmp = tmp->next;
    
    // If ther has only one node
    if(index == 1){
        free(head);
        return NULL;
    }
    
    // Find the last N_th node and the last N+1_th node
    for(int count = 0 ; count < index - n ; count++){
        last = preN;
        preN = preN->next;
    }
    
    // Checking if we want to remove the head
    if(index - n){
        last->next = preN->next;
        free(preN);
    }
    else
        head = head->next;
    
    return head;
}

## Complexity

- Way 1 & 2

|Space |Time |
|- |- |
|$O(1)$|$O(N)$|

## Result

- Way 1
- Runtime : 8 ms, 14.14 % of c submissions
- Memory usage : 5.9 MB, 28.68 % of c submissions
- Way 2
- Runtime: 3 ms, faster than 70.76%
- Memory Usage: 5.8 MB, less than 50.55%