Remove Nth Node from the end of Linked List

In this article, we aim to remove the N-th node from the end of a singly linked list. This is a common problem in linked list manipulation, often asked in coding interviews.

Example:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

N = 2

Output:

1 -> 2 -> 3 -> 5 -> NULL

Problem Statement: Given the head of a linked list, remove the N-th node from the end of the list and return its head.

Solution:

To solve this problem efficiently, we can use the two-pointer technique. Let us understand this before going ahead with the code.

Steps to Solve:

1.    Initialize Two Pointers:

·        Use two pointers, fast and slow, both initially pointing to the head of the list.

2.    Advance the Fast Pointer:

·        At first move the fast pointer N steps ahead.

3.    Move Both Pointers:

·        Now we move both fast and slow pointers one step at a time until the fast pointer reaches the end of the list. By this time, the slow pointer will be at the node that is 1 node before the N-th node from the end.

4.    Remove the Target Node:

·        Now we remove the node which comes after slow as that is our target node.

Time Complexity: O(N)

Space Complexity: O(1)