This approach involves two passes through the linked list to find the node that needs to be removed. In the first pass, compute the length of the list. In the second pass, remove the (Len - n + 1)th node from the start of the list by maintaining a pointer to manage node deletions properly.
Time Complexity: O(L), where L is the length of the linked list since we pass over the list twice (to calculate length and to remove the node).
Space Complexity: O(1) since no additional data structures other than few pointers are used.
1function ListNode(val, next) {
2 this.val = (val===undefined ? 0 : val);
3 this.next = (next===undefined ? null : next);
4}
5
6var getLength = function(head) {
7 let length = 0;
8 while (head !== null) {
9 length++;
10 head = head.next;
11 }
12 return length;
13};
14
15var removeNthFromEnd = function(head, n) {
16 let length = getLength(head);
17 let dummy = new ListNode(0, head);
18 let current = dummy;
19 for (let i = 0; i < length - n; i++) {
20 current = current.next;
21 }
22 current.next = current.next.next;
23 return dummy.next;
24};The JavaScript implementation adopts the same two-step strategy. It first calculates the total node count, utilizes a dummy node to ensure seamless deletions, and removes the required element by adjusting pointers on the second pass.
This approach uses two pointers, fast and slow. Begin by moving the fast pointer n steps ahead. Then move both pointers simultaneously until fast reaches the end. This provides the correct position to remove the nth node from the end efficiently in one go.
Time Complexity: O(L), where L stands for the list's total node count.
Space Complexity: O(1), since a fixed amount of pointers are manipulated.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
8 dummy = ListNode(0, head)
9 fast = slow = dummy
10 for _ in range(n + 1):
11 fast = fast.next
12 while fast:
13 fast = fast.next
14 slow = slow.next
15 slow.next = slow.next.next
16 return dummy.nextIn Python, the one-pass solution engages two pointers, advancing fast first by n nodes. Following this lead, fast and slow traverse concurrently, ensuring slow's position is optimal for the necessary node removal.