Reversing the list changes the direction, making the nth node from the end become the nth node from the start of the reversed list. Once reversed, we can easily traverse forward to find and delete the required node.
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head ==null)
returnnull;
//get length of list ListNode p = head;
int len = 0;
while (p !=null) {
len++;
p = p.next;
}
//if remove first nodeint fromStart = len - n + 1;
if (fromStart == 1)
return head.next;
//remove non-first node p = head;
int i = 0;
while (p !=null) {
i++;
if (i == fromStart - 1) {
p.next= p.next.next;
}
p = p.next;
}
return head;
}
Method 3 - One Pass - Using Slow and Fast Pointers#
Utilize fast and slow pointers, positioning the fast pointer n steps ahead of the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the element just before the target. This method is often referred to as the frame-based solution.
We can first run the code similar to Find Nth Node From End Of Linked List, with some modifications. Firstly, we prepend the list with the dummy node, and slow pointer will point to it.
classSolution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// Create a dummy node to handle edge cases ListNode dummy =new ListNode(0);
dummy.next= head;
ListNode first = dummy;
ListNode second = dummy;
// Move `first` pointer n + 1 steps aheadfor (int i = 0; i <= n; i++) {
first = first.next;
}
// Move `first` and `second` pointers until `first` reaches the endwhile (first !=null) {
first = first.next;
second = second.next;
}
// Remove the nth node from the end second.next= second.next.next;
return dummy.next; // Return the head of the modified linked list }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
defremoveNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) # Create a dummy node to handle edge cases first = dummy
second = dummy
# Move `first` pointer n + 1 steps aheadfor _ in range(n +1):
first = first.next
# Move `first` and `second` pointers until `first` reaches the endwhile first:
first = first.next
second = second.next
# Remove the nth node from the end second.next = second.next.next
return dummy.next # Return the head of the modified linked list
Here found is passed by reference and is updated again and again. When we reach the end of the linked list, it is set to 1, otherwise it is incremented by 1.