Remove Kth Node From End From Linked List | LeetCode - Leetcode Solution

Given linked list: 1->2->3->4->5, and k = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

To remove the kth node from the linked list, first step is traversing to the (k-1)th node in the linked list. After that, we just need to rewire the pointers and make the next of k-1th node point to the (k+1)th node.

We can do that in one pass by using an algorithm similar to How to find middle element of linked list in one iteration?

We will create two pointers, fast and and slow pointers. At the start of the algorithm , slow pointer will point towards the first node of the linked list, and the fast pointer will point towards the (K + 1)th node of the linked list.

After that, we will start iterating over the linked list and increment both the slow pointer and the fast pointer by 1 position each until the fast pointer reaches the end as shown in the diagram below:

When the fast pointer reaches end, the slow pointer will reach the kth element from end, and we can delete it by using normal delete operation.

1