148.排序链表

链接：148.排序链表
难度：Medium
标签：链表、双指针、分治、排序、归并排序
简介：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

题解 1 - typescript

• 编辑时间：2020-11-21
• 执行用时：156ms
• 内存消耗：53.5MB
• 编程语言：typescript
• 解法介绍：利用内置排序算法。

function sortList(head: ListNode | null): ListNode | null {
  if (head == null) return null;
  const arr: ListNode[] = [];
  let temp: ListNode | null = head;
  while (temp !== null) {
    arr.push(temp);
    temp = temp.next;
  }
  const len = arr.length;
  arr
    .sort(({ val: val1 }, { val: val2 }) => val1 - val2)
    .forEach((node, i, arr) => {
      node.next = arr[i + 1] ?? null;
    });
  return arr[0];
}

题解 2 - typescript

• 编辑时间：2021-05-13
• 执行用时：164ms
• 内存消耗：56.7MB
• 编程语言：typescript
• 解法介绍：归并思想排序。

function sortList(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  const list: ListNode[] = [];
  let p: ListNode | null = head;
  while (p !== null) {
    list.push(p);
    p = p.next;
  }
  const len = list.length;
  const sort = (start: number, end: number) => {
    if (end - start < 2) return;
    const mid = (start + end) >> 1;
    sort(start, mid);
    sort(mid, end);
    merge(start, mid, end);
  };
  const merge = (start: number, mid: number, end: number) => {
    const tempList = list.slice(start, mid);
    let p1 = 0;
    let p2 = mid;
    let i = start;
    while (p1 < mid - start) {
      if (p2 >= end || tempList[p1].val <= list[p2].val) {
        list[i++] = tempList[p1++];
      } else {
        list[i++] = list[p2++];
      }
    }
  };
  sort(0, len);
  let i = 0;
  for (; i < len - 1; i++) list[i].next = list[i + 1];
  list[i].next = null;
  return list[0];
}