Real Constant Space! 9 variables total, no recursion


  • 0
    public ListNode sortList(ListNode head) {
    	if (head == null || head.next == null)
    		return head;
    
    	int N = 0;
    	ListNode p = head;
    	while (p != null) {
    		N++;
    		p = p.next;
    	}
    
    	ListNode dummy = new ListNode(Integer.MIN_VALUE);
    	dummy.next = head;
    	ListNode pre = dummy;
    	ListNode p1 = head;
    	ListNode p2 = p1;
    	ListNode p3 = p2.next;
    	int size = 1;
    	int count = 0;
    
    	while (size < N ) {
    		pre = dummy;
    		p1 = pre.next;
    		p2 = p1;
    		p3 = p2;
    		
    		while (p1 != null) {
    			count = size;
    			while (count != 0 && p2.next != null) {
    				count--;
    				p2 = p2.next;
    			}
    			if (count > 0) {
    				pre.next = p1;
    				break;
    			}
    
    			p3 = p2;
    			count = size;
    			while (count != 0 && p3 != null) {
    				count--;
    				p3 = p3.next;
    			}
    
    			pre = merge(pre, p1, size, p2, size - count);
    
    			if (p3 == null || count != 0)
    				break;
    
    			p1 = p3;
    			p2 = p1;
    		}
    		size *= 2;
    	}
    
    	return dummy.next;
    }
    
    public ListNode merge(ListNode pre, ListNode p1, int size1, ListNode p2,
    		int size2) {
    	pre.next = p1;
    	while (size1 != 0 && size2 != 0) {
    		if (p2.val < p1.val) {
    			pre.next = p2;
    			p2 = p2.next;
    			pre.next.next = p1;
    			pre = pre.next;
    			size2--;
    		} else {
    			pre = p1;
    			p1 = p1.next;
    			size1--;
    		}
    	}
    
    	if (size2 == 0) {
    		while (size1 != 0) {
    			pre = pre.next;
    			size1--;
    		}
    		pre.next = null;
    		return pre;
    	}
    
    	if (size1 == 0) {
    		pre.next = p2;
    		while (size2 != 0) {
    			pre = pre.next;
    			size2--;
    		}
    	}
    
    	return pre;
    }

  • 0

    Would be nice if you wrote at least a short overview about how it works.


Log in to reply
 

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