本题来自Leetcode，题目传送门：力扣

难度：中等

编程语言：Go

1. 题目介绍

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

插入排序算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

3. 重复直到所有输入数据插入完为止。 下面是插入排序算法的一个图形示例。

部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

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

提示：

1. 列表中的节点数在 [1, 5000]范围内

2. -5000 <= Node.val <= 5000

2. 解题思路

由于是链表，所以需要记录表头，后续每一个需要插入的元素都需要从表头开始比对。其次插入条件，比前一位大，比后一位小于或者等于。 链表插入后，需要更新前一个节点的Next指针，还要连接后续没有排序的节点。

3. 源码展示

编码之前，先写好测试:

func Test_insertionSortList(t *testing.T) {
	head1 := &ListNode{}
	head1.Val = 4
	next := &ListNode{Val: 2}
	head1.Next = next
	next.Next = &ListNode{Val: 1}
	next = next.Next
	next.Next = &ListNode{Val: 3}
	next = next.Next

	rHead1 := &ListNode{}
	rHead1.Val = 1
	next = &ListNode{Val: 2}
	rHead1.Next = next
	next.Next = &ListNode{Val: 3}
	next = next.Next
	next.Next = &ListNode{Val: 4}
	next = next.Next

	head2 := &ListNode{}
	head2.Val = -1
	next = &ListNode{Val: 5}
	head2.Next = next
	next.Next = &ListNode{Val: 3}
	next = next.Next
	next.Next = &ListNode{Val: 4}
	next = next.Next
	next.Next = &ListNode{Val: 0}
	next = next.Next

	rHead2 := &ListNode{}
	rHead2.Val = -1
	next = &ListNode{Val: 0}
	rHead2.Next = next
	next.Next = &ListNode{Val: 3}
	next = next.Next
	next.Next = &ListNode{Val: 4}
	next = next.Next
	next.Next = &ListNode{Val: 5}
	next = next.Next

	inputs := []*ListNode{head1, head2}
	expects := []*ListNode{rHead1, rHead2}

	for i := 0; i < len(inputs); i++ {
		got := insertionSortList(inputs[i])
		expected := expects[i]
		if !ListNodeEqual(got, expected) {
			t.Logf("[%d] want ", i+1)
			expected.print()
			t.Logf(",got ")
			got.print()
			t.Fatal()
		}
	}
}

func ListNodeEqual(head1, head2 *ListNode) bool {
	if head1.Val != head2.Val {
		return false
	}
	if !(head1.Next != nil && head2.Next != nil) {
		return true
	}
	return ListNodeEqual(head1.Next, head2.Next)
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func (head *ListNode) print() {
	fmt.Print(head.Val)
	next := head.Next
	for next != nil {
		fmt.Printf(" ,%d", next.Val)
		next = next.Next
	}
	fmt.Println()
}

方法实现

func insertionSortList(head *ListNode) *ListNode {
   if head == nil {
      return nil
   }
   rHead := &ListNode{Val: 0, Next: head}
   end := head
   current := head.Next
   for current != nil {
      if current.Val >= end.Val {
         //直接下一个
         end = end.Next
         current = current.Next
         continue
      }

      // 插入之前，保存短点
      end.Next = current.Next

      insertNode := rHead
      for insertNode.Next.Val < current.Val {
         insertNode = insertNode.Next
      }

      //插入到insertNode后面
      current.Next = insertNode.Next
      insertNode.Next = current
      current = end.Next

   }
   return rHead.Next
}

Leetcode运算结果 ：

执行用时: 4 ms

内存消耗: 3.1 MB

生活依然要继续，每天拿出半个小时，放下焦虑，用行动来积累更好的自己，我们一起加油！