Category: Medium
Problem
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Follow up: Could you do this in one pass?
https://leetcode.com/problems/remove-nth-node-from-end-of-list
Examples
Example 1:
1 2 | Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] |
Example 2:
1 2 | Input: head = [1], n = 1 Output: [] |
Example 3:
1 2 | Input: head = [1,2], n = 1 Output: [1] |
Solution Approach
In this problem of “remove nth node from the list”, we are given a linked list whose length is not given and we are also given a number which is the position of the element we have to remove from the end of the list which makes this problem a little tricky.
We can use 2 ways to tackle this problem – one is to count the number of elements in the list then pass through it again to remove the element or the second which is to use two pointers to track and delete the element. We will discuss more the same below.
Two-Pass method
In this method, we will go through all the element once to calculate the length (suppose l is the length of the list) of the linked list and then start from the beginning to remove the element which is at (l-n)th place in the list and return the list as the answer. Since we are passing through the linked list twice hence our time complexity of this approach is O(2n). The space complexity is O(1) since we are not using any extra space for this problem.
Coming to the code we create a node to act as the 0th index of the list called the initial node. Then we create a pointer that will be used to iterate through the whole list. Let’s call it current and point it to the head node. We also have to create a variable to store the value of the size of the list. Then iterate this current node through the whole Linked List using a while loop and keep increasing the value of the size variable until the end of the list is achieved.
We decrease the value of size by n. Secondly, use the initial node to point to the node before the head. Then iterate till we reach the spot where the removal is required. After that, we remove the element by removing the link from the previous element and then return the initial head as the answer.
One Pass Method
In this method, we will only pass through the linked list only once but using two pointers. The pointers will be n nodes apart. This is done so that if one pointer reaches the end of the list the other pointer will reach the element which is to be removed. We can achieve this by moving one pointer n steps initially and then starting the next pointer parallelly. So when the first pointer reaches the end of the list the second pointer points to the node which has to be removed. The time complexity is O(n) since it’s passing only once and the space complexity of this approach is O(1) because we are not using any extra space.
The code for this approach is pretty straightforward we create an initial node so that it acts as the 0th index before the head. Then we create two pointers which will point initially to the initial node of the list. Let’s call them first and second and we move the first pointer by n nodes. Then we keep iterating both pointers together till the first pointer reaches the end i.e it becomes null. In the end, we remove the link of the required node using the second pointer. Lastly, we return the head node as the answer.
Solution code
Two-Pass Method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode initial = new ListNode(-1); initial.next = head; ListNode current = head; int size = 0; while(current != null){ size++; current = current.next; } size -= n; current = initial; while(size > 0){ size--; current = current.next; } current.next = current.next.next; return head; } } |
One Pass Method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode initial = new ListNode(-1); initial.next = head; ListNode first = initial, second = initial; for (int i = 0; i <= n; i++) first = first.next; while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return head; } } |
For more Leetcode explained solutions visit Leetcode Solutions.
If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Leetcoding 🙂