Java Bottom-up Iterative Merge Sort easy to understand : O(n*logn) time, O(1) space


  • 0
    K

    Here is my Java solution : bottom-up iteratively merge sort a LinkedList
    Time complexity : O(n*log(n))
    Space complexity : O(1); no recursion because iterative bottom-up is used; in-place because it's a LinkedList

    public class Solution {
    	public ListNode sortList(ListNode head) {
    		// Calculate length of the list
    		int len = length(head);
    
    		// dummy's next node is always the updated head (min node)
    		ListNode dummy = new ListNode(0);
    		dummy.next = head;
    		for (int size = 1; size < len; size *= 2) {
    			// Head of left sub-list
    			ListNode head1 = dummy.next;
    			ListNode tail = dummy;
    			while (head1 != null) {
    				tail.next = head1;
    				// Head of right sub-list
    				ListNode head2 = moveSize(head1, size);
    				if (head2 != null) {
    					ListNode nextHead = moveSize(head2, size);
    					tail = merge(tail, head1, head2);
    					head1 = nextHead;
    				} else {
    					break;
    				}
    			}
    		}
    		return dummy.next;
    	}
    
    	private int length(ListNode head) {
    		int len = 0;
    		ListNode cur = head;
    		while (cur != null) {
    			cur = cur.next;
    			len++;
    		}
    		return len;
    	}
    
    	// Get the node that is size to the right of the head
    	private ListNode moveSize(ListNode head, int size) {
    		ListNode newHead = head;
    		for (int i = 0; i < size; i++) {
    			if (newHead == null)
    				return null;
    			if (i == size - 1) {
    				// Set tail to null
    				ListNode tmp = newHead.next;
    				newHead.next = null;
    				newHead = tmp;
    			} else {
    				newHead = newHead.next;
    			}
    		}
    		return newHead;
    	}
    
    	// merge two sorted linkedlist and return the new tail of merged list
    	private ListNode merge(ListNode tail, ListNode head1, ListNode head2) {
    		while (head1 != null && head2 != null) {
    			if (head1.val < head2.val) {
    				tail.next = head1;
    				tail = tail.next;
    				head1 = head1.next;
    			} else {
    				tail.next = head2;
    				tail = tail.next;
    				head2 = head2.next;
    			}
    		}
    		// link to the non-empty list
    		if (head1 == null)
    			tail.next = head2;
    		if (head2 == null)
    			tail.next = head1;
    		// move to the end
    		while (tail.next != null)
    			tail = tail.next;
    		return tail;
    	}
    }
    

Log in to reply
 

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