147.对链表进行插入排序

链接：147.对链表进行插入排序
难度：Medium
标签：链表、排序
简介：对链表进行插入排序。

题解 1 - typescript

• 编辑时间：2020-11-20
• 执行用时：128ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：遍历两次进行插入。

function insertionSortList(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  const tempHead = new ListNode(0, head);
  let last = head;
  let p = head.next;
  last.next = null;
  while (p !== null) {
    const next = p.next;
    add(p);
    p = next;
  }
  return tempHead.next;
  function add(node: ListNode): void {
    let temp = tempHead;
    const val = node.val;
    while (temp.next !== null && temp.next !== last) {
      if (temp.next.val < val) {
        temp = temp.next;
      } else {
        node.next = temp.next;
        temp.next = node;
        return;
      }
    }
    if (temp.next === last) {
      if (last.val > val) {
        node.next = temp.next;
        temp.next = node;
      } else {
        last.next = node;
        node.next = null;
        last = node;
      }
    }
  }
}