removeNthFromEnd<T> function

LinkedListNode<T>? removeNthFromEnd<T>(LinkedListNode<T>? head, int n)

Removes the nth node from the end of the linked list

head - The head of the linked list n - The position from the end (1-indexed) Returns the new head of the linked list

Time Complexity: O(n) where n is the length of the list Space Complexity: O(1)

Implementation

LinkedListNode<T>? removeNthFromEnd<T>(LinkedListNode<T>? head, int n) {
  if (head == null || n <= 0) return head;

  // Create a dummy node to handle edge cases
  LinkedListNode<T> dummy = LinkedListNode<T>(head.value);
  dummy.next = head;

  LinkedListNode<T>? first = dummy;
  LinkedListNode<T>? second = dummy;

  // Move first pointer n+1 steps ahead
  for (int i = 0; i <= n; i++) {
    if (first == null) return head; // n is greater than list length
    first = first.next;
  }

  // Move both pointers until first reaches the end
  while (first != null) {
    first = first.next;
    second = second!.next;
  }

  // Remove the nth node from end
  second!.next = second.next!.next;

  return dummy.next;
}