Sort a linked list using insertion sort.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

思路

---

　　这道题意思就是让你使用插入排序来对链表进行排序，根据插入排序在数组的思想，我们可以知道他是将数组分成两部分，排序好的，未排序的。我们每次都从没排序的数组中提取一个数字将其插入到排序好的数组。直到未排序的数组个数为0。如果将其运用到链表中，其思想也是一样的可以详细见图示步骤和解决代码。时间复杂度为O(n2), 空间复杂度为O(1)
图示步骤

---

解决代码

---

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def insertionSortList(self, head):
 9         """
10         :type head: ListNode
11         :rtype: ListNode
12         """
13         if not head:
14             return head
15         cur = head
16         while cur.next:     # 循环结束条件
17             if cur.next.val < cur.val:       # 如果下一个节点的值比当前节点值大，则需要将其插入到相应的位置
18                 tem_cur = cur.next            # 将cur.next节点独立出来，
19                 cur.next = cur.next.next       # 后cur.next下一个节点连接起来。
20                 tem_head = head
21                 if tem_head.val >= tem_cur.val:    # 从头节点开始查找合适的插入位置，如果cur.next的值小于头节点的值直接插入到头节点中。
22                     tem_cur.next = head
23                     head = tem_cur
24                 else:                                # 否者遍历查找合适的位置
25                     while tem_head.next.val < tem_cur.val:
26                         tem_head = tem_head.next
27                     t_next = tem_head.next             # 将节点插入到合适的位置
28                     tem_head.next = tem_cur
29                     tem_cur.next = t_next
30             else:                         # 说明cur.next的值大于cur的值，更新cur的值，直接遍历下一个节点
31                 cur = cur.next         
32         return head                    # 返回头节点。