链表排序

排序算法：归并排序

思路：

二分法递归函数：去中间值
while 条件判断函数：左右两边进行对比

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

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

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

  /* 1. 去中间值 */
    // 慢指针
    let middle = node;
    // 快指针
    let fast = node.next;

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

  /* 2. 分割左右链表 */
    let rightList = middle.next;
    // 从中间切断
    middle.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
      //上面两步等价于数组连接：result.push(left.shift());
    } else {
      pre.next = right
      right = right.next
      //上面两步等价于数组连接：result.push(right.shift());
    }
    pre = pre.next;
  }

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

console.log(mergeSort(head))

链表排序

排序算法：归并排序​

排序算法：归并排序