Not sure whether my code has constant space


  • 2
    C

    I am new to this website. I just think this one can be easily resolved by using Java array's sort function. So I just convert those into an array and use java's sort function to resolve it. Based on Java Arrays' documentation, it takes O(nlgn) time.
    And my solution gets accepted.
    But it does not document its space. And I am not sure my implementation are using the constant space or not. Anyone can help me?

    public class Solution {
        public ListNode sortList(ListNode head) {
            //Return if the list is empty or has only one node.
    		if (head == null || head.next == null) {
    			return head;
    		}
    
    		//Create a list to hold all the node.
    		List<MyListNode> myNodeList = new ArrayList<MyListNode>();
    		ListNode tempNode = head;
    		while (tempNode != null) {
    			myNodeList.add(new MyListNode(tempNode));
    			tempNode = tempNode.next;
    		}
    		
    		//Copy the list into an array and sort the array.
    		MyListNode[] myListNodeArray = myNodeList
    				.toArray(new MyListNode[myNodeList.size()]);
    		Arrays.sort(myListNodeArray);
    		
    		//Re-link all the nodes in the linked list. 
    		for (int i = 0; i < myListNodeArray.length - 1; i++) {
    			myListNodeArray[i].listNode.next = myListNodeArray[i + 1].listNode;
    		}
    		myListNodeArray[myListNodeArray.length - 1].listNode.next = null;
    		
    		//Return the first node.
    		return myListNodeArray[0].listNode;
        }
        
        private class MyListNode implements Comparable<MyListNode> {
    		ListNode listNode;
    
    		public MyListNode(ListNode listNode) {
    			this.listNode = listNode;
    		}
    
    		@Override
    		public int compareTo(MyListNode o) {
    			return ((Integer) listNode.val).compareTo((Integer) o.listNode.val);
    		}
    	}
    }

  • 0
    V

    O(n) space complexity as an ArrayList of size equal to input list length is created. As size of input list grows asymptotically auxiliary space created for myNodeList grows in proportional to n


Log in to reply
 

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