[Leetcode 19]Remove Nth Node From End of List

2 min readSep 16, 2021

Description:

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

C code solution 1:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    // if only one node, return NULL    if(head->next == NULL)
        return NULL;
    struct ListNode* ptr = head;
    int steps = 0;    // find how many steps from head to tail    while(ptr->next != NULL){
        steps++;
        ptr = ptr->next;
    }    //update steps to the number of steps from head to the previous node of the target node    steps = steps - n;
    ptr = head;// if steps < 0, meaning the target node is the head, so return the next node    if(steps < 0){
        return head->next;
    }// Otherwise, walk to the previous node of the target node and bypass the target node    else{
        while(steps){
            steps--;
            ptr = ptr->next;
        }
        ptr->next = ptr->next->next;
    }
    
    return head;
}

Explanation:

先確認linked list長度，再將長度減掉n來確定走到target remove node的前一個node需要幾步，再走到那個node，最後進行node removal。

C code solution 2:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* nsteps = head;
    struct ListNode* ptr = head;
    struct ListNode* prev = NULL;
    
    // make n distance between ptr and nsteps
    
    while(n > 0 && nsteps != NULL){
        nsteps = nsteps->next;
        n--;
    }
    
    //start to walk nsteps to the end. Meanwhile, move ptr to keep n distance between them
    
    while(nsteps != NULL){
        prev = ptr;
        ptr = ptr -> next;
        nsteps = nsteps->next;
    }
    
    // remove ptr
    
    // if the remove target is the first node, return the next noe of the head
    
    if(ptr == head){
        return head->next;
    }
    
    //else remove ptr
    
    else{
        prev->next = ptr->next;
    }
    
    return head;
}

Explanation:

利用三個指標 prev ptr nsteps ，prev 指到remove target的前一個node，ptr 指到remove target，nsteps 會指到tail。一開始先將ptr nsteps 這兩個取好n的距離，接著讓nsteps 帶著其他pointer走直到tail，這樣以來ptr 就會剛好指向要被remove target。

[Leetcode 19]Remove Nth Node From End of List

Written by Samuel Liu