题目大意
通过插入排序的方法排序一个链表。
解题思路
参考：http://www.cnblogs.com/zuoyuan/p/3700105.html
- 用current往后找，找到比之前小的数。
- 每次都用pre从dummy开始，找到该插入的位置，插入。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
dummy = ListNode(0)
dummy.next = head
curr = head
while curr.next:
if curr.next.val < curr.val: # 直到某数小于其前面的数，进入
pre = dummy # 回到头开始往后遍历
while pre.next.val < curr.next.val: # 用pre直到找到应该插入的位置
pre = pre.next
# 如上图
tmp = curr.next # 把2保存到temo
curr.next = tmp.next # 把4指向2的后面一位
tmp.next = pre.next # 2指向3
pre.next = tmp # 1指向2
else:
curr = curr.next
return dummy.next
|
总结