Sort Linked List — Merge Sort in O(N log N)

Algorithm

Node sort(Node head) {
  if (head == null || head.next == null) return head;
  Node mid = findMiddleAndSplit(head);
  Node left = sort(head);
  Node right = sort(mid);
  return merge(left, right);
}

Split at middle

Find middle with fast/slow. Set middle-1's next to null. Return middle as new head of right half.

Complexity

O(N log N) time, O(log N) space for recursion stack. Iterative variant achieves O(1) space.

Bottom-up iterative

Merge sublists of size 1, then 2, 4, 8… No recursion. True O(1) auxiliary space.