How to Solve Remove Nth Node from End of List
Remove Nth Node from End of List Introduction
Remove Nth Node from End of List Introduction
Remove Nth Node from End of List problem as the name implies asks us given the head of a linked list and a value N, remove the Nth node from the end of the list, and return its head. This problem can be solved simply in one traversal by using two pointers, a fast and a slow pointer.
Remove Nth Node from End of List Problem
Remove Nth Node from End of List Problem
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example Inputs and Outputs
Example 1
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2
Input: head = [1], n = 1
Output: []
Example 3
Input: head = [1,2], n = 1
Output: [1]
Remove Nth Node from End of List Solutions
Remove Nth Node from End of List Solutions
To solve this problem, we can use a two-pointer approach. We'll initialize two pointers, fast and slow, both pointing to the head of the linked list. We'll move the fast pointer n steps ahead, creating a gap of n nodes between fast and slow. Then, we'll move both pointers simultaneously until the fast pointer reaches the end of the linked list.
At this point, the slow pointer will be pointing to the nth node from the end. To remove this node, we'll adjust the next pointers accordingly. If the node to be removed is the head itself, we'll update the head to the next node. Otherwise, we'll set the slow.next pointer to skip the nth node and point to the next node.
def removeNthFromEnd(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Move fast pointer n steps ahead
for _ in range(n):
fast = fast.next
# Move both pointers simultaneously until fast reaches the end
while fast.next:
fast = fast.next
slow = slow.next
# Remove the nth node by adjusting the next pointers
slow.next = slow.next.next
return dummy.next1def removeNthFromEnd(head, n):
2 dummy = ListNode(0)
3 dummy.next = head
4
5 fast = slow = dummy
6
7 # Move fast pointer n steps ahead
8 for _ in range(n):
9 fast = fast.next
10
11 # Move both pointers simultaneously until fast reaches the end
12 while fast.next:
13 fast = fast.next
14 slow = slow.next
15
16 # Remove the nth node by adjusting the next pointers
17 slow.next = slow.next.next
18
19 return dummy.nextTime/Space Complexity Analysis
- Time Complexity: O(N), where N is the length of the linked list, as we only iterate through the list once.
- Space Complexity: O(1), as we are using a constant amount of extra space for the two pointers and the dummy node.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
