My ac solution python


  • 0
    S
    class Solution:
        # @param head, a ListNode
        # @return a ListNode
        def sortList(self, head):
            #constant space
            if head is None:
                return
            copy = []
            pr = head
            #O(n)
            while pr is not None:
                copy.append((pr.val, pr))
                pr = pr.next
            # copy contains val and address of one node
            copy = sorted(copy)#O(nlgn) time can use quick sort
            for i in range(len(copy)-1):
                _, adr = copy[i]
                adr.next = copy[i+1][1]
            copy[-1][1].next = None
            head = copy[0][1]
            return head

  • 0
    C

    This is easy but I don't think this is constant space.


  • 0
    S

    yes you're right it's O(N) space


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.