Is my solution valid?

  • 0

    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 =
       = None
            nodes.sort(key=lambda n: n.val)
            while nodes:
                node = nodes.pop()
       = head
                head = node
            return head

  • 0

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

  • 0

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

  • 0

    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.