一、简介

单链表的插入排序

输入：

{30,20,40}

返回值：

{20,30,40}

二、解法

思路：利用插入排序，如下:

func insertionSortList(head *ListNode) *ListNode {
   // write code here
   if head == nil || head.Next == nil {
      return head
   }

   p := head
   // 每次将 p.Next插入队列
   for p.Next != nil {
      // 端口 p.next 节点
      node := p.Next

      // 将当前节点作为新的列表头节点
      if node.Val < head.Val {
         p.Next = p.Next.Next
         node.Next = head
         head = node

         continue
      }

      // 找出node 应该在的位置
      p1 := head
      p2 := p1.Next

      for p2 != node {
         if p2.Val > node.Val {
            break
         }

         p1 = p1.Next
         p2 = p2.Next
      }

      // 将node 插入 p1, 和 p2之间
      if p2 != node {
         p.Next = p.Next.Next

         p1.Next = node
         node.Next = p2

         continue
      }

      // 不需要移动，接着判断链表下个节点
      p = p.Next
   }

   return head
}

题目来源于牛客网