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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9int getLength(struct ListNode *head) {
10 int length = 0;
11 while (head) {
12 length++;
13 head = head->next;
14 }
15 return length;
16}
17
18struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
19 int length = getLength(head);
20 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
21 dummy->next = head;
22 struct ListNode* current = dummy;
23 for (int i = 0; i < length - n; i++) {
24 current = current->next;
25 }
26 struct ListNode *toDelete = current->next;
27 current->next = current->next->next;
28 free(toDelete);
29 struct ListNode *newHead = dummy->next;
30 free(dummy);
31 return newHead;
32}This C implementation carries out the Two-Pass Technique. First, it uses a helper function getLength() to compute the length of the list. Then, it iterates to the node immediately before the node to be removed using a dummy node to handle edge cases more efficiently. After removal, it returns the new head of the linked list.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
10 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
11 dummy->next = head;
12 struct ListNode *fast = dummy, *slow = dummy;
13 for (int i = 0; i <= n; i++) {
14 fast = fast->next;
15 }
16 while (fast) {
17 fast = fast->next;
18 slow = slow->next;
19 }
20 struct ListNode* toDelete = slow->next;
21 slow->next = slow->next->next;
22 free(toDelete);
23 struct ListNode* newHead = dummy->next;
24 free(dummy);
25 return newHead;
26}The C implementation employs two pointers, fast and slow, to move through the list. Initially, the fast pointer is moved n+1 steps for gap creation. As both pointers proceed together, the slow pointer effectively lands at the one preceding the removable node. The code adjusts pointers easily when the fast pointer exhausts the list, ensuring the linked list structure remains valid after node removal.