import { ListNode } from "../../lib/list-node.js";

export function sortList(head) {
  if (!head?.next) return head;
  const getLength = (h) => {
    let n = 0;
    for (; h; h = h.next) n++;
    return n;
  };
  const split = (h, n) => {
    for (let i = 1; h && i < n; i++) h = h.next;
    if (!h) return null;
    const rest = h.next;
    h.next = null;
    return rest;
  };
  const merge = (a, b) => {
    const dummy = ListNode(0);
    let t = dummy;
    while (a && b) {
      if (a.val <= b.val) {
        t.next = a;
        a = a.next;
      } else {
        t.next = b;
        b = b.next;
      }
      t = t.next;
    }
    t.next = a ?? b;
    return dummy.next;
  };
  const len = getLength(head);
  const dummy = ListNode(0, head);
  for (let size = 1; size < len; size *= 2) {
    let tail = dummy;
    let cur = dummy.next;
    while (cur) {
      const left = cur;
      const right = split(left, size);
      cur = split(right, size);
      const merged = merge(left, right);
      tail.next = merged;
      while (tail.next) tail = tail.next;
    }
  }
  return dummy.next;
}
148. Sort List — O(n log n) time, O(1) extra: bottom-up merge sort.
