insertAtPosition<T> function

LinkedListNode<T>? insertAtPosition<T>(LinkedListNode<T>? head, T value, int position)

Inserts a new node with the given value at the specified position

head - The head of the linked list value - The value to insert position - The position where to insert (0-indexed) Returns the new head of the linked list

Time Complexity: O(n) where n is the position Space Complexity: O(1)

Implementation

LinkedListNode<T>? insertAtPosition<T>(
  LinkedListNode<T>? head,
  T value,
  int position,
) {
  // Handle insertion at the beginning
  if (position == 0) {
    LinkedListNode<T> newNode = LinkedListNode<T>(value);
    newNode.next = head;
    return newNode;
  }

  // Handle invalid position
  if (position < 0) return head;

  LinkedListNode<T>? current = head;
  int currentPosition = 0;

  // Traverse to the position before where we want to insert
  while (current != null && currentPosition < position - 1) {
    current = current.next;
    currentPosition++;
  }

  // If we reached the end before the position, return original head
  if (current == null) return head;

  // Insert the new node
  LinkedListNode<T> newNode = LinkedListNode<T>(value);
  newNode.next = current.next;
  current.next = newNode;

  return head;
}