对链表进行插入排序

01. 移除重复节点

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

示例 1:

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

示例 2:

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

代码

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

class ListNode {
  constructor(val, next) {
    this.val = val
    this.next = next || null
  }
}

function insertionSortList(head) {
  var dummyNode = new ListNode(-1, head)
  var pre = dummyNode
  var fast = dummyNode
  while (fast) {
    var next = fast.next

    if (next != null && next.val < fast.val) {
      while (pre.next.val < next.val) {
        pre = pre.next
      }

      // 交换位置
      fast.next = next.next
      next.next = pre.next
      pre.next = next

      // 重置dummyNode
      pre = dummyNode
    }

    fast = next
  }
  return dummyNode.next
}

console.log(insertionSortList(head))