Remove the N-th node from the end of a linked list

Hi there 😊 !!! Glad to see you and thank you for taking the time to give this article a look.

To stay notified about more such articles make sure you subscribe to my newsletter.

This Question Is from Leetcode

Description: Given a Linked List and a number n, write a function that removes the value at the n-th node from the end of the Linked List.

Kindly note: We have been given the head of a linked list so we don't have to create a list on our own. We are only subject to remove the N-th node from the end, that's it.

Example 1:

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

Output: [1, 2, 3, 5]

Example 2: Screenshot 2020-10-06 at 8.29.20 PM.png

Example 3: Screenshot 2020-10-06 at 8.28.01 PM.png

If we think about the input and output of the first example we can note that, we have to drop the N-th node from the end which means we have to point the (N-1)th node to the (N+1)th node.

Visually this can be put together as:

One Pass Algorithm:

Why are we calling this one pass algorithm now? It's because we traverse the linked list only once in this algorithm to do our job, unlike the two pass algorithm in which we would have to calculate the length of the list first and then traverse the list second time to remove the N-th node from the end. 😊

Declare two pointers both at the head position of the linked list namely fast and slow. (You may choose any names as per your choice though 😊)

Move the fast pointer n times such that it points to the (N+1)th place from the start.
Then advance both the pointers simultaneously by one such that the fast points to the NULL (i.e. end of the linked list) and as consequence we should also note that the slow pointer points to the N-th node from the last.

Now that the fast pointer is pointing to NULL we should point the node prior to the slow pointer to node after slow pointer which would remove the node in between from the linked list.

You may also consider storing the node prior to the slow node using another pointer for ease of understanding.

Javascript Solution:

const removeNthFromEnd = (head, n) => {
      let fast = head,
             slow = head,
              prev = head; /* used for the purpose of better readability and understanding */

      for (let i = 0; i < n; i++) {  
        /* so that the fast pointer points the (N+1)th node from the start. */
            fast = fast.next;
      }

      while (fast !== null) { 
        /* keep a check on fast, if it is not null do whatever is in the body of while. */
            fast = fast.next; /* advance 'fast' by one position */
            prev = slow;  /* store the node prior to slow, so that we could point it to (N+1)th Node */
            slow = slow.next;  /* advance 'slow' by one position */
      }

      if (slow == head) {  /* handling the edge case, size of linked list is one as in the 3rd example above */
            return slow.next;  /* the function will return from here if the case is true */
      }

      prev.next = slow.next;  /* point N-1-th to N+1-th from the end */
      return head;
};

Time Complexity: O(n); Since we may need to traverse the N nodes of the linked list to find the solution.

Space Complexity: O(1); Since we only need three pointers, regardless of how many elements the list contains.

Thank you for reading till the end 😇.

If you found that I've missed something kindly drop a comment below, you can also share your valuable feedback/communicate with me via twitter.

If you'll want me to make more such content, let me know too.

Make sure to share this if you found it helpful, and keep learning, you're a genius.

Remove the N-th node from the end of a linked list

Other articles I'll recommend you to read: