# LeetCode 148. Sort list

Title:

Under O(n log n) time complexity and constant level space complexity, the linked list is sorted.

Train of thought:

Using merge idea, but the sorting of linked list is different from that of array. Array can be directly obtained in the middle index, and linked list must be searched with fast or slow pointer.
In addition, the time complexity and space responsibility required by this problem are also relatively high, often overtime.

Explanation:
It's overtime and needs to be improved.

```class Solution:
def sortList(self, head: ListNode) -> ListNode:
while fast and fast.next:
fast,slow = fast.next.next,slow.next #Two steps for fast pointer and one step for slow pointer during traversal
#When the fast pointer reaches the end point, the slow pointer reaches the middle point and blocks the list.
mid,slow.next = slow,None
right = self.sortList(mid)

return self.merge2Lists(left,right)

def merge2Lists(self, left: ListNode, right: ListNode) -> ListNode:
if not left:return right
if not right:return left
if left.val < right.val:
left.next = self.merge2Lists(left.next, right)
return left
else:
right.next = self.merge2Lists(left, right.next)
return right```

```class Solution:
def sortList(self, head: ListNode) -> ListNode: