The O(n) Club: Linked List to BST—the Only Speed Limit is Your Pointer

The O(n) Club: Linked List to BST—the Only Speed Limit is Your Pointer

⚡ TL;DR

Turning a sorted singly-linked list into a balanced BST? Sure, here’s the naive recipe: march the fast and slow pointer parade to grab the middle node (in O(n)), split, and recurse until you run out of list or willpower. Works, but it’s not winning any marathons. Snippet, anyone?

// Classic brute: Find middle on every call (ouch)
public TreeNode sortedListToBST(ListNode head) {
  if (head == null) return null;
  if (head.next == null) return new TreeNode(head.val);
  ListNode slow = head, fast = head, prev = null;
  while (fast != null && fast.next != null) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  if (prev != null) prev.next = null; // split list
  TreeNode root = new TreeNode(slow.val);
  root.left = sortedListToBST(head == slow ? null : head);
  root.right = sortedListToBST(slow.next);
  return root;
}

🧠 How Devs Usually Mess This Up

No judgment (we’ve all done it), but most folks pretend a linked list is an array. They reach for the middle like it’s free candy, forgetting you have to trudge node-by-node each time. Brute-forcing the middle gives you an O(n log n) time bill—plus, you might fall into the trap of thinking you can build your BST “in place.” Nope. You’re building a whole new tree, whether you like it or not.

🔍 What’s Actually Going On

Think of the list as a tightrope: you can walk forward, but there’s no jumping to the middle unless you want a face full of Big O. “Fast and slow” gets you there eventually, but doing it for every subtree smells like inefficiency. Want elegance (and a cocktail at the interviewer’s VIP lounge)? Stash values in an array (cheat code) or—if you crave that algorithmic respect—simulate in-order traversal and use a global pointer. It’s like doing tree surgery and reading the book at the same time, one chapter per node.

🛠️ PseudoCode

• Count total nodes (prepare for some quality time with your pointer):

  int size = 0;
  ListNode curr = head;
  while (curr != null) {
    size++;
    curr = curr.next;
  }
  

  One lap, no surprises.

• Recursively build your tree, always using a moving pointer that advances as you “insert” the node’s value:

  TreeNode buildBST(int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    TreeNode leftChild = buildBST(left, mid - 1);
    TreeNode root = new TreeNode(pointer.val);
    pointer = pointer.next;
    root.left = leftChild;
    root.right = buildBST(mid + 1, right);
    return root;
  }
  

  Pointer does one smooth pass, no backtracking or drama.

• Profit. It’s literally a tree-growing assembly line—your pointer builds nodes like a robot on autopilot.

💻 The Code

// Java: O(n) time & O(log n) space (recursion stack only)
class Solution {
    private ListNode pointer;
    public TreeNode sortedListToBST(ListNode head) {
        int size = 0;
        ListNode curr = head;
        while (curr != null) {
            size++;
            curr = curr.next;
        }
        pointer = head;
        return buildBST(0, size - 1);
    }
    private TreeNode buildBST(int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode leftChild = buildBST(left, mid - 1);
        TreeNode root = new TreeNode(pointer.val);
        pointer = pointer.next;
        root.left = leftChild;
        root.right = buildBST(mid + 1, right);
        return root;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t get cute and “index” into your list. It’s not a Netflix episode—there’s no skipping ahead without a sequential trek.
• If you hack up the list over and over to find middles, your runtime is crying (O(n log n)).
• Edge cases? Yes, handle that empty/null input and identical values—make sure your BST is still balanced, even if boring.
• Recursion stack is O(log n), so unless you’re allergic to call stacks, it’s memory-friendly. (In-order array copy? That’s O(n) extra space but sometimes easier for a brain on too much coffee.)

🧠 Interviewer Brain-Tattoo

“If you need O(1) access to a middle node, congratulations, you want an array, not a linked list. (Interviewers love in-order simulation—try it, you’ll look so algorithmic.)”