Is my solution valid?


  • 0
    Y

    The idea is to use O(n) to convert between linked list and array. Then use system-sort, which I assume is O(n lg n). Since I have not create any new node, I think it is O(1) space (or whatever it takes for the system-sort). Is my solution cheating?

    class Solution:
        # @param head, a ListNode
        # @return a ListNode
        def sortList(self, head):
            nodes = []
            while head:
                node = head
                head = head.next
                node.next = None
                nodes.append(node)
            nodes.sort(key=lambda n: n.val)
            while nodes:
                node = nodes.pop()
                node.next = head
                head = node
            return head

  • 0
    L

    You use list in your code , which is at least O(n) space complexity


  • 0
    Y

    but my list was empty, and every element was moved from the linked list


  • 0
    Y

    maybe you are right, say, every element in the nodes list is a new pointer to the existing nodes in the linked list. So I have created n new pointers?


Log in to reply
 

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