148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3] 输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]

示例 3：

输入：head = [] 输出：[]

答案

思路：

1. 先将链表分割成最小的块
2. 在放入合并 -> 从最小的块升序排序

数组转链表

// [4,2,1,3]

const head = {
   'val':4,
   'next':{
         'val':2,
         'next':{
               'val':1,
               'next':{
                     'val':3,
                     'next':undefined
               }
         }
   }
}

排序

class ListNode{
  constructor(val, next){
    this.val = (val===undefined ? 0 : val)
     this.next = (next===undefined ? null : next)
  }
}

// 切分列表
const mergeSort = (node) => {
    // 若无链表 -> 直接返回
    if(!node || !node.next) return node;

    // 慢指针
    let mid = node;
    // 快指针
    let fast = node.next;

    // 利用fast和fast.next
    // 如果链表长度为奇数，则返回中间节点
    // 如果链表长度为偶数，则有两个中间节点，这里返回第一个
    while(fast && fast.next){
        mid = mid.next;
        fast = fast.next.next;
    }

    // 分割左右链表
    let rightList = mid.next;
    // 从中间切断
    mid.next = null;
    let left = node;
    let right = rightList;
    // 继续分割到只有一个时 -> 传入mergeList合并方法
    return merge(mergeSort(left),mergeSort(right));
}

// 合并两个有序链表
const merge = (left,right) => {
  // 从最小的块开始合并
  let result = new ListNode(0);

  let pre = result;
  // 左右都存在
  while (left && right) {

    // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
    if (left.val <= right.val) {
      pre.next = left
      left = left.next
    } else {
      pre.next = right
      right = right.next
    }
    pre = pre.next;
  }

  // 最大值
  pre.next = left || right;
  // 返回最后的结果
  return result.next;
}

const head = {
  val: 4,
  next: {
    val: 2,
    next: {
      val: 1,
      next: {
        val: 3,
        next: null
      }
    }
  }
}

console.log(mergeSort(head))

结合（待）

https://leetcode.cn/problems/sort-list/solution/-by-1105389168-a8lp/