三个月算法进阶--day34

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head # termination.
        # cut the LinkedList at the mid index.
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None # save and cut.
        # recursive for cutting.
        left, right = self.sortList(head), self.sortList(mid)
        # merge `left` and `right` linked list and return it.
        h = res = ListNode(0)
        while left and right:
            if left.val < right.val: h.next, left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        target = head.val
        ans = ListNode(target)
        ptr = head.next
        small, large = ListNode(), ListNode()
        h1, h2 = small, large
        while ptr:
            temp = ptr.next
            if ptr.val < target:
                h1.next = ptr
                h1 = h1.next
                h1.next = None
            else:
                h2.next = ptr
                h2 = h2.next
                h2.next = None
            ptr = temp
        left = self.sortList(small.next)
        right = self.sortList(large.next)
        h = left
        if not h:
            ans.next = right
            return ans
        while h.next:
            h = h.next
        h.next, h.next.next = ans, right
        return left

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        target = head.val
        ptr = head
        small, equal, large = None, None, None
        while ptr:
            temp = ptr.next
            if ptr.val < target:
                ptr.next = small
                small = ptr
            elif ptr.val > target:
                ptr.next = large
                large = ptr
            else:
                ptr.next = equal
                equal = ptr
            ptr = temp
        left = self.sortList(small)
        right = self.sortList(large)

        ret = ListNode()
        cur = ret
        for node in (left, equal, right):
            if node:
                cur.next = node
                node = node.next
                cur = cur.next
            while node:
                node = node.next
                cur = cur.next
        return ret.next