Last Updated: 22 Oct, 2020
Delete Kth Node From End
Moderate
Asked in companies
You have been given a singly Linked List of 'N' nodes with integer data and an integer 'K'.
Your task is to remove the 'K'th node from the end of the given Linked List and return the head of the modified linked list.
Example:
Input : 1 -> 2 -> 3 -> 4 -> 'NULL' and 'K' = 2
Output: 1 -> 2 -> 4 -> 'NULL'
Explanation:
After removing the second node from the end, the linked list become 1 -> 2 -> 4 -> 'NULL'.
Input format :
The first line contains an integer 'N', the size of the linked list and an integer 'K'.
The second line contains 'N' space-separated integers.
Output format :
The output contains the linked list after deletion. If the list is empty, -1 is printed.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up:
Can you solve this without finding the length of the linked list and using O(1) extra space?
Approaches
The naive solution is to process all the nodes from the front side of the linked list and keep adding a node to the list. Now we can easily remove the Kth node from the end of the list by simply replacing the next pointer of the ('LENGTH' - 'K' - 1)th node (0-based indexing from start) of the list with the ('LENGTH' - 'K' + 1)th node. This way we can remove the Kth node from the end of the linked list.
- Find the length of Linked List 'L'
- Check if 'L' = 'K' then remove the head by assigning head to head’s next node.
- Else start iterating through the linked list until it comes to ('L' - 'K' -1 )th(0 based indexing from start) node. We will remove the ('L' - 'K')th node by relinking the next pointer of ('L' - 'K' - 1)th node to the ('L' - 'K' + 1)th node.
We can remove the required node without finding the length of the given linked list by using two pointers 'SLOW' and 'FAST', which are 'K' nodes apart from each other.
- Initially, the 'FAST' pointer advances the list by 'K' nodes from the beginning and the 'SLOW' is a pointer to the head of the linked list.
- Now both pointers are exactly separated by 'K' distance from each other. We will maintain a constant gap by advancing both pointers together until the 'FAST' pointer reaches the last node.
- When the 'FAST' pointer is at the last node then the 'SLOW' pointer will be at ('K' + 1)th node from the end of the linked list.
- At last, we will set the next of 'SLOW' pointer to its next of next node.