tags: leetcode medium Linked List Two Pointers

19. 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%