题解 | #单链表的排序#

BM12 单链表的排序

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类 the head node
 * @return ListNode类
 */
function sortInList(head) {
  // write code here
  if (!head || !head.next) return head;
  let start = head;
  let end = head.next;
  //   end 以两个节点向后，所以判断 end 和 end.next 都存在时继续循环
  while (end && end.next) {
    start = start.next;
    end = end.next.next;
  }
  //   此时 start 在中间位置
  //   右边的链表
  let newList = start.next;
  start.next = null;
  //   递归拆分左右的链表
  let left = sortInList(head);
  let right = sortInList(newList);
  //   合并两个链表
  let result = Merge(left, right);

  return result;
}

// 递归调用合并两个有序列表方法
function Merge(pHead1, pHead2) {
  if (!pHead1) return pHead2;
  if (!pHead2) return pHead1;
  if (pHead1.val <= pHead2.val) {
    pHead1.next = Merge(pHead1.next, pHead2);
    return pHead1;
  } else {
    pHead2.next = Merge(pHead1, pHead2.next);
    return pHead2;
  }
}

module.exports = {
  sortInList: sortInList,
};

如有问题望指正