leetcode 【 Insertion Sort List 】 python 实现
题目：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一下逻辑，发现完全是无用判断浪费时间，去掉后就通过了。
页:
[1]