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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def getLength(self, head: ListNode) -> int:
8 length = 0
9 while head:
10 length += 1
11 head = head.next
12 return length
13
14 def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
15 length = self.getLength(head)
16 dummy = ListNode(0, head)
17 current = dummy
18 for _ in range(length - n):
19 current = current.next
20 current.next = current.next.next
21 return dummy.nextThis Python implementation uses a similar approach by leveraging a helper function to calculate the length of the linked list. A dummy node is used for straightforward logic when adjusting pointers. After finding the correct position, it links the node before and after the nth node from the end, effectively removing it.
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.
1function ListNode(val, next) {
2 this.val = (val===undefined ? 0 : val);
3 this.next = (next===undefined ? null : next);
4}
5
6var removeNthFromEnd = function(head, n) {
7 let dummy = new ListNode(0);
8 dummy.next = head;
9 let fast = dummy;
10 let slow = dummy;
11 for (let i = 0; i <= n; i++) {
12 fast = fast.next;
13 }
14 while (fast !== null) {
15 fast = fast.next;
16 slow = slow.next;
17 }
18 slow.next = slow.next.next;
19 return dummy.next;
20};The JavaScript version utilizes fast pointers pre-moved by n nodes, allowing one-pass execution once both pointers proceed concurrently. Upon fast's null state, slow ensures the needed linkage adjustments to omit the nth end-node.