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 int val;
3 ListNode next;
4 ListNode() {}
5 ListNode(int val) { this.val = val; }
6 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7}
8
9class Solution {
10 public int getLength(ListNode head) {
11 int length = 0;
12 while (head != null) {
13 length++;
14 head = head.next;
15 }
16 return length;
17 }
18
19 public ListNode removeNthFromEnd(ListNode head, int n) {
20 int length = getLength(head);
21 ListNode dummy = new ListNode(0);
22 dummy.next = head;
23 ListNode current = dummy;
24 for (int i = 0; i < length - n; i++) {
25 current = current.next;
26 }
27 current.next = current.next.next;
28 return dummy.next;
29 }
30}The Java solution adopts a very similar strategy to the C++ and C versions. It calculates the size of the linked list before iterating to find and remove the nth node from the end. A dummy node is used to simplify pointer manipulation and return the new head safely.
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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val = 0, ListNode next = null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode RemoveNthFromEnd(ListNode head, int n) {
12 ListNode dummy = new ListNode(0, head);
13 ListNode fast = dummy, slow = dummy;
14 for (int i = 0; i <= n; i++) {
15 fast = fast.next;
16 }
17 while (fast != null) {
18 fast = fast.next;
19 slow = slow.next;
20 }
21 slow.next = slow.next.next;
22 return dummy.next;
23 }
24}This C# solution utilizes pointers, leveraging an upfront n step advance for fast before concurrently stepping through the list. As fast runs out, slow is optimally stationed to adjust the list connections, facilitating removal with ease.