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:
            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

Answer questions:

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

 

Posted on Mon, 07 Oct 2019 04:12:02 -0700 by heavenly