148. Sort List

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 分解：将列表分成两半
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # 递归排序左半部分
    right_half = merge_sort(arr[mid:])  # 递归排序右半部分

    # 合并：将两个有序子列表合并
    return merge(left_half, right_half)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

// 找到中间节点
// divide linked list
const middleNode = (head) => {
  let slow = head
  let fast = head
  let pre = head
  while (fast && fast.next) {
    pre = slow //记录slow前一个节点
    slow = slow.next
    fast = fast.next.next
  }
  pre.next = null
  return slow
}

// 合并两个有序数组
const mergeLinkedList = (head1, head2) => {
  if (head1 === null) {
    return head2
  } else if (head2 === null) {
    return head1
  } else if (head1.val > head2.val) {
    head2.next = mergeLinkedList(head1, head2.next)
    return head2
  } else {
    head1.next = mergeLinkedList(head1.next, head2)
    return head1
  }
}

var sortList = function (head) {
  // 归并排序
  // 空或者只有一个节点不用排序
  if (head === null || head.next === null) {
    return head
  }
  const middle = middleNode(head)
  const left = sortList(head)
  const right = sortList(middle)
  return mergeLinkedList(left, right)
}