📑 题目：147. 对链表进行插入排序

🚀 本题 LeetCode 传送门

题目大意

链表的插入排序

解题思路

按照题意做即可。

代码

package leetcode
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
 if head == nil {
  return head
 }
 newHead := &ListNode{Val: 0, Next: nil} // 这里初始化不要直接指向 head，为了下面循环可以统一处理
 cur, pre := head, newHead
 for cur != nil {
  next := cur.Next
  for pre.Next != nil && pre.Next.Val < cur.Val {
   pre = pre.Next
  }
  cur.Next = pre.Next
  pre.Next = cur
  pre = newHead // 归位，重头开始
  cur = next
 }
 return newHead.Next
}