147. Insertion Sort List

题目

给定一个链表头，使用插入排序将这个链表排序，返回排序后的链表头部。

解析

对于一个给定的链表，要使用插入排序排序该链表，需要确定一个已排序的链表区间。
根据链表的使用经验，新增一个虚拟标头 vhead 有利于编码和逻辑整洁。所以使用一个 vhead 标识已排序链表的起点，使用 vtail 标识已排序链表的结尾。
从前往后进行插入排序，当指针指向 vtail 时，将新值直接插入末尾，成为新的 vtail。否则和指针的下一个元素进行比较，如果比下一个元素小，则插入下一个元素前边。

终止条件:
当 vtail 的下一个元素为空时，整个排序终止。

伪代码

vhead.next = head
vtail = vhead
target = vtail.next
for target = vtail.next; target != nil; target=vtail.next
  // 剪切当前元素
  vtail.next = target.next
  // 寻找一个插入的位置
  for cur = vhead; cur != vtail; cur=cur.next
    if target < cur.next
      break
  target.next = cur.next
  cur.next = target

 // 是否更新 vtail
  if cur == vtail
      vtail = vtail.next

代码

func insertionSortList(head *ListNode) *ListNode {
    vhead := &ListNode{Next: head}
    vtail := vhead
    
    for target := vtail.Next; target != nil; target = vtail.Next {
        vtail.Next = target.Next
        
        cur := vhead
        for ; cur != vtail; cur = cur.Next {
            if target.Val < cur.Next.Val {
                break
            }
        }
        target.Next = cur.Next
        cur.Next = target
        
        if cur == vtail {
            vtail = vtail.Next
        }
    }
    return vhead.Next
}