- Notifications
You must be signed in to change notification settings - Fork 306
/
Copy pathsortList.py
86 lines (71 loc) · 2.33 KB
/
sortList.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
# Author: Yu Zhou
# 148. Sort List
# Sort a linked list in O(n log n) time using constant space complexity.
# 思路
# 用链表的方式切分，然后递归Split，之后Merge
# 这道题要注意是切分的时候，要写个Prev的函数用来储存Slow的原点
# Time: O(nlogn)
# Space: O(1)
# ****************
# Final Solution *
# ****************
classSolution(object):
defsortList(self, head):
ifnotheadornothead.next:
returnhead
prev=None
fast=slow=head
whilefastandfast.next:
prev=slow
slow=slow.next
fast=fast.next.next
mid=slow
prev.next=None#截断
l=self.sortList(head) #递归
r=self.sortList(mid)
returnself.merge(l, r)
#这是一种类似于创建一个头的DummyNode，把Head设置成Prev，Cur设置成head.next
defmerge(self, l, r):
guard=cur=ListNode(None)
whilelandr:
ifl.val<=r.val:
cur.next=l
l=l.next
else:
cur.next=r
r=r.next
cur=cur.next
cur.next=lorr
returnguard.next
vhead=curr=ListNode(0)
whilel1andl2:
ifl1.val<=l2.val:
curr.next=l1
l1=l1.next
else:
curr.next=l2
l2=l2.next
curr=curr.next
curr.next=l1orl2
returnvhead.next
# ***************************************
# The following code is an fail attempt *
# ***************************************
classSolution(object):
defsortList(self, head):
ifnotheadornothead.next:
returnhead
fast=slow=head
#这里错在没有设置一个prev来保存Slow的值
#每次while结束后，slow就会变成slow.next
#假如想在slow的地方切断，就必须设置一个Prev
#来保存slow的值，下方 mid = slow.next
#其实已经是在经历过while 后的slow.next的next了
whilefastandfast.next:
slow=slow.next
fast=fast.next.next
mid=slow.next
slow.next=None#截断
l=self.sortList(head) #递归
r=self.sortList(mid)
returnself.merge(l, r)
