148 Sort List
# 148 Sort List
题目来源:
https://leetcode.com/problems/sort-list/description/
题意分析:
Sort a linked list in O(n log n) time using constant space complexity.
对一个链表进行排序,时间复杂度为O(n log n) ,空间复杂度为常量。
题目思路:
学了python之后,偷懒的机会越来越多了,直接用list.sort()的时间复杂度正是O(n log n),进行一下转换即可。
代码:
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. def sortList(self, head):
9. """
10. :type head: ListNode
11. :rtype: ListNode
12. """
13. l=[]
14. trace=head
15. while(trace):
16. l.append(trace.val)
17. trace=trace.next
18.
19. l.sort()
20.
21. index=0
22. trace=head
23. while(trace):
24. trace.val=l[index]
25. index=index+1
26. trace=trace.next
27.
28. return head
提交细节: