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

难度：中等

编程语言：Go

1. 题目介绍

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

插入排序算法的步骤:

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

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

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

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

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

提示：

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

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

2. 解题思路

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

3. 源码展示

编码之前，先写好测试:

func Test_insertionSortList(t *testing.T) {nthead1 := &ListNode{}nthead1.Val = 4ntnext := &ListNode{Val: 2}nthead1.Next = nextntnext.Next = &ListNode{Val: 1}ntnext = next.Nextntnext.Next = &ListNode{Val: 3}ntnext = next.NextnntrHead1 := &ListNode{}ntrHead1.Val = 1ntnext = &ListNode{Val: 2}ntrHead1.Next = nextntnext.Next = &ListNode{Val: 3}ntnext = next.Nextntnext.Next = &ListNode{Val: 4}ntnext = next.Nextnnthead2 := &ListNode{}nthead2.Val = -1ntnext = &ListNode{Val: 5}nthead2.Next = nextntnext.Next = &ListNode{Val: 3}ntnext = next.Nextntnext.Next = &ListNode{Val: 4}ntnext = next.Nextntnext.Next = &ListNode{Val: 0}ntnext = next.NextnntrHead2 := &ListNode{}ntrHead2.Val = -1ntnext = &ListNode{Val: 0}ntrHead2.Next = nextntnext.Next = &ListNode{Val: 3}ntnext = next.Nextntnext.Next = &ListNode{Val: 4}ntnext = next.Nextntnext.Next = &ListNode{Val: 5}ntnext = next.Nextnntinputs := []*ListNode{head1, head2}ntexpects := []*ListNode{rHead1, rHead2}nntfor i := 0; i < len(inputs); i++ {nttgot := insertionSortList(inputs[i])nttexpected := expects[i]nttif !ListNodeEqual(got, expected) {ntttt.Logf("[%d] want ", i+1)ntttexpected.print()ntttt.Logf(",got ")ntttgot.print()ntttt.Fatal()ntt}nt}n}nnfunc ListNodeEqual(head1, head2 *ListNode) bool {ntif head1.Val != head2.Val {nttreturn falsent}ntif !(head1.Next != nil && head2.Next != nil) {nttreturn truent}ntreturn ListNodeEqual(head1.Next, head2.Next)n}nntype ListNode struct {ntVal intntNext *ListNoden}nnfunc (head *ListNode) print() {ntfmt.Print(head.Val)ntnext := head.Nextntfor next != nil {nttfmt.Printf(" ,%d", next.Val)nttnext = next.Nextnt}ntfmt.Println()n}nnn

方法实现

func insertionSortList(head *ListNode) *ListNode {n if head == nil {n return niln }n rHead := &ListNode{Val: 0, Next: head}n end := headn current := head.Nextn for current != nil {n if current.Val >= end.Val {n //直接下一个n end = end.Nextn current = current.Nextn continuen }nn // 插入之前，保存短点n end.Next = current.Nextnn insertNode := rHeadn for insertNode.Next.Val < current.Val {n insertNode = insertNode.Nextn }nn //插入到insertNode后面n current.Next = insertNode.Nextn insertNode.Next = currentn current = end.Nextnn }n return rHead.Nextn}

Leetcode运算结果 ：

执行用时: 4 ms

内存消耗: 3.1 MB

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