leetcode 【 Insertion Sort List 】 python 实现

tubaobaoya3

　　题目：
　　Sort a linked list using insertion sort.
　　
　　代码：oj测试通过 Runtime: 860 ms



1 # Definition for singly-linked list.
2 # class ListNode:
3 #     def __init__(self, x):
4 #         self.val = x
5 #         self.next = None
6
7 class Solution:
8     # @param head, a ListNode
9     # @return a ListNode
10     def insertionSortList(self, head):
11         
12         
13         if head is None or head.next is None:
14             return head
15         
16         dummyhead = ListNode(0)
17         dummyhead.next = head
18         
19         curr = dummyhead.next
20         while curr.next is not None:
21             if curr.next.val < curr.val:
22                 pre = dummyhead
23                 while pre.next.val < curr.next.val:
24                     pre = pre.next
25                 tmp = curr.next
26                 curr.next = tmp.next
27                 tmp.next = pre.next
28                 pre.next = tmp
29             else:
30                 curr = curr.next
31         
32         return dummyhead.next
　　思路：
　　首先要知道插入排序的原理。
　　对于单链表来说，需要做指针的交换。
　　小白记忆插入排序的原理只有一句话：类比扑克牌抓牌，把牌按大小插入。
　　需要注意的地方是
　　
　　不要加多余的判断，否则会超时；第一次运行的时候，我在里面的while循环条件判断上加了一句 pre != curr，结果就报超时了。
　　check一下逻辑，发现完全是无用判断浪费时间，去掉后就通过了。