Use merge sort, O(n*lg(n)), but still can't pass, ANY suggestions?


  • 0
    D

    I've checked it several times, I still think my solution meet the requirement.

    The idea come from merge sort. ( bottum up way)
    for length 2,4,6,8,... ------------------ ( O(lg(n)) times
    we detach list 1 and list 2 from original list. --------------------- ( O(n)) times
    And merge list 1 and list 2. ------------ ( O(n)) times

    public class SortList {
    	public ListNode sortList(ListNode head) {
    		// use the merge sort idea, but iteratively
    		// on i_th time, we use merge 2^(i-1) , nodes with another
    
    		// get the size of list
    		if (head == null)
    			return head;
    		int nNodes = 0;
    		ListNode runner = head;
    		while (runner != null) {
    			nNodes++;
    			runner = runner.next;
    		}
    		int nInteration = (int) (Math.log(nNodes)/Math.log(2))+1;
    		
    		// list in header is ascending order
    		ListNode header = new ListNode(Integer.MAX_VALUE);
    		ListNode newHeader = new ListNode(Integer.MAX_VALUE);
    
    		ListNode header1 = new ListNode(Integer.MAX_VALUE);
    		ListNode header2 = new ListNode(Integer.MAX_VALUE);
    
    		header.next = head;
    		for (int i = 0; i < nInteration; i++) { // log(n) times
    			// merge position 2^i , and the next 2^i nodes
    			runner = header.next;
    			newHeader.next = null; // reseting the new List
    			ListNode tailOfNewHeader = newHeader;
    			while (runner != null) {// run a iteration
    				// detach list 1
    				header1.next = header.next;
    				header2.next = null;
    				// runner would point to the last node of list 1 ( or null if
    				// exceed)
    				for (int j = 0; j < Math.pow(2, i) - 1; j++) {
    					if (runner.next != null) {// detach and append on
    						runner = runner.next;
    					} else {
    						break;
    					}
    				}
    				// , detach list1 from header ,and and detach list 2
    				header.next = runner.next;
    				runner.next = null; // make tail of list1 ( header1) point to null
    				// detach list 2
    				header2.next = header.next;
    				runner = header.next;
    				for (int j = 0; j < Math.pow(2, i)-1; j++) {
    					if (runner != null) {// detach and append on
    						runner = runner.next;
    					} else {
    						break;
    					}
    				}
    				if (runner == null) {
    					header.next = null;
    				} else {
    					header.next = runner.next;
    					runner.next = null; // to make the tail of list2 pointing to
    										// null
    				}
    				// merge by adding on the tail of header
    				tailOfNewHeader = mergeAndAppend(header1, header2,
    						tailOfNewHeader);
    				runner = header.next; // making runner pointing to
    			}
    			header.next = newHeader.next;
    		}
    		return header.next;
    	}
    
    	private ListNode mergeAndAppend(ListNode header1, ListNode header2,
    			ListNode tail) {
    		// add all list in header1 and header 2, after tail
    		ListNode tmp;
    		while (header1.next != null && header2.next != null) {
    			if (header1.next.val < header2.next.val) {
    				tmp = header1.next;
    				header1.next = header1.next.next;
    			} else {
    				tmp = header2.next;
    				header2.next = header2.next.next;
    			}
    			tail.next = tmp;
    			tail = tmp;
    			tail.next = null;
    		}
    		if (header1.next == null) {
    			tail.next = header2.next;
    		} else {
    			tail.next = header1.next;
    		}
    		// make tail point to the last
    		while (tail.next != null) {
    			tail = tail.next;
    		}
    		return tail;
    	}
    }

  • 0
    K

    Can you explain the idea of your algorithm? You mention you do it iteratively. How?


Log in to reply
 

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