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.
It's overtime and needs to be improved.
class Solution: def sortList(self, head: ListNode) -> ListNode: if not (head and head.next): return head fast,slow = head.next,head # 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 left = self.sortList(head) 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: if not (head and head.next): return head pre, slow, fast = None, head, head while fast and fast.next: pre, slow, fast = slow, slow.next, fast.next.next pre.next = None return self.mergeTwoLists(*map(self.sortList, (head, slow))) def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2