#148. 排序链表

// sortList 函数接收链表头节点 head，返回排序后的链表头节点
var sortList = function (head) {
  // 如果链表为空，或者链表只有一个节点，说明已经有序，直接返回
  if (head === null || head.next === null) {
    // 返回当前链表头节点，作为递归的终止结果
    return head;
  }

  // slow 是慢指针，用来寻找链表中点，初始指向头节点
  let slow = head;
  // fast 是快指针，每次走两步；从 head.next 开始可以让 slow 停在左半部分的尾节点
  let fast = head.next;

  // 当 fast 还能继续向后走时，说明 slow 还没有到达中间位置
  while (fast !== null && fast.next !== null) {
    // slow 每次只走一步
    slow = slow.next;
    // fast 每次走两步
    fast = fast.next.next;
  }

  // slow.next 是右半部分链表的头节点，需要先保存下来
  const rightHead = slow.next;
  // 将 slow.next 置为 null，把原链表断开成左右两个独立链表
  slow.next = null;

  // 递归排序左半部分链表，head 仍然是左半部分的头节点
  const left = sortList(head);
  // 递归排序右半部分链表，rightHead 是右半部分的头节点
  const right = sortList(rightHead);

  // 将两个已经有序的链表合并，并返回合并后的头节点
  return merge(left, right);
};

// merge 函数接收两个升序链表 list1 和 list2，返回合并后的升序链表
function merge(list1, list2) {
  // 创建虚拟头节点，方便统一处理结果链表的第一个节点
  const dummy = new ListNode(0);
  // cur 指向结果链表的尾节点，后续新接入的节点都挂在 cur.next 上
  let cur = dummy;

  // 当两个链表都还有节点时，持续比较两个链表当前节点的值
  while (list1 !== null && list2 !== null) {
    // 如果 list1 当前节点的值更小或相等，就把 list1 当前节点接到结果链表后面
    if (list1.val <= list2.val) {
      // cur.next 指向 list1 当前节点，完成节点拼接
      cur.next = list1;
      // list1 指针后移，准备比较 list1 的下一个节点
      list1 = list1.next;
    } else {
      // 否则说明 list2 当前节点更小，就把 list2 当前节点接到结果链表后面
      // cur.next 指向 list2 当前节点，完成节点拼接
      cur.next = list2;
      // list2 指针后移，准备比较 list2 的下一个节点
      list2 = list2.next;
    }

    // cur 后移到结果链表的最新尾节点
    cur = cur.next;
  }

  // 循环结束后，至少有一个链表已经为空；另一个链表剩余部分本身已经有序，直接接上即可
  cur.next = list1 === null ? list2 : list1;

  // dummy 是虚拟头节点，真正的排序结果从 dummy.next 开始
  return dummy.next;
}