Leetcode 19. Remove Nth Node From End of List
Problem Explanation
The problem is to remove the nth node from the end of a given linked list. The linked list can be any length and the nth node to be removed is counted from the end.
Consider a linked list 1->2->3->4->5 and say we want to remove the 2nd node from the end, which is 4.
Approach
The idea is to leverage two pointers: fast and slow pointers.
Initially, both pointers point to the start of the linked list. First, we advance the fast pointer n nodes ahead. Then we move both the slow and fast pointers one node a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the (n+1)th node from the end.
Now, since we want to remove nth node from the end, the node to remove will be the one after the slow pointer. So we direct the slow pointer's next pointer to point to the next node's next node (skipping over the node to be removed), thus effectively removing the nth node from the end of the linked list.
Solution
Python
1 2python 3class Solution: 4 def removeNthFromEnd(self, head, n): 5 slow = fast = head 6 for _ in range(n): 7 fast = fast.next 8 if not fast: 9 return head.next 10 while fast.next: 11 slow = slow.next 12 fast = fast.next 13 slow.next = slow.next.next 14 return head
Java
1 2java 3public class Solution { 4 public ListNode removeNthFromEnd(ListNode head, int n) { 5 ListNode slow = head, fast = head; 6 for(int i=1; i<=n; i++){ 7 fast = fast.next; 8 if(fast == null) 9 return head.next; 10 } 11 while(fast.next != null){ 12 slow = slow.next; 13 fast = fast.next; 14 } 15 slow.next = slow.next.next; 16 17 return head; 18 } 19}
Javascript
1 2javascript 3class Solution { 4 removeNthFromEnd(head, n) { 5 let slow = head, fast = head; 6 for(let i=0; i<n; i++){ 7 fast = fast.next; 8 if(fast == null) 9 return head.next; 10 } 11 while(fast.next != null){ 12 slow = slow.next; 13 fast = fast.next; 14 } 15 slow.next = slow.next.next; 16 17 return head; 18 } 19}
C++
1 2c++ 3class Solution { 4public: 5 ListNode* removeNthFromEnd(ListNode* head, int n) { 6 ListNode* slow = head; 7 ListNode* fast = head; 8 9 while (n--) 10 fast = fast->next; 11 12 if (fast == nullptr) 13 return head->next; 14 15 while (fast->next) { 16 slow = slow->next; 17 fast = fast->next; 18 } 19 slow->next = slow->next->next; 20 21 return head; 22 } 23};
C#
1 2csharp 3public class Solution { 4 public ListNode RemoveNthFromEnd(ListNode head, int n) { 5 ListNode slow = head, fast = head; 6 for(int i=0; i<n; i++){ 7 fast = fast.next; 8 if(fast == null) 9 return head.next; 10 } 11 while(fast.next != null){ 12 slow = slow.next; 13 fast = fast.next; 14 } 15 slow.next = slow.next.next; 16 17 return head; 18 } 19}
The time complexity of the above solution is O(L), where L is the length of the linked list. The space complexity is O(1), as we are only using two pointers.### Ruby
1 2ruby 3class Solution 4 def remove_nth_from_end(head, n) 5 slow = fast = head 6 n.times { 7 fast = fast.next 8 return head.next unless fast 9 } 10 while fast.next 11 slow = slow.next 12 fast = fast.next 13 end 14 slow.next = slow.next.next 15 16 head 17 end 18end
Swift
1 2swift 3class Solution { 4 func removeNthFromEnd(_ head: ListNode?, _ nthNode: Int) -> ListNode? { 5 let dummy: ListNode? = ListNode(0) 6 dummy?.next = head 7 var first: ListNode? = dummy 8 var second: ListNode? = dummy 9 10 for i in 1...nthNode+1 { 11 first = first?.next 12 } 13 14 while first != nil { 15 first = first?.next 16 second = second?.next 17 } 18 19 second?.next = second?.next?.next 20 21 return dummy?.next 22 } 23}
PHP
1 2php 3class Solution 4{ 5 function removeNthFromEnd($head, $n) { 6 $slow = $fast = $head; 7 for($i = 0; $i < $n; $i++){ 8 $fast = $fast->next; 9 if($fast === null) 10 return $head->next; 11 } 12 while($fast->next !== null){ 13 $slow = $slow->next; 14 $fast = $fast->next; 15 } 16 $slow->next = $slow->next->next; 17 18 return $head; 19 } 20}
Each solution uses the same logic: two pointers, fast and slow, are employed. The fast pointer advances n steps first, then both pointers take steps together until the fast pointer reaches null. At this point, the slow pointer is at the previous node of the nth node from the end, and we can delete the nth node by adjusting the slow node's next pointer. This allows us to traverse the linked list only once, resulting in a time complexity of O(L), where L is the length of the linked list and space complexity is O(1).
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.