[LeetCode 148]Sort List

/**
 * 
	Sort a linked list in O(n log n) time using constant space complexity.
 *
 */

public class SortList {

	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
	//解法一 ： 歸並法
	
//	15 / 15 test cases passed.
//	Status: Accepted
//	Runtime: 310 ms
//	Submitted: 0 minutes ago
	//時間復雜度O(n * log(n)) 空間復雜度 O(1)
    public ListNode sortList(ListNode head) {
    	if(head == null || head.next == null) {
    		return head;
    	}
    	ListNode slow = head;
    	ListNode fast = head;
    	//找到鏈表的中點位置
    	while(fast.next != null && fast.next.next != null) {
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	fast = slow.next;
    	//斷開鏈表
    	slow.next = null;
    	
    	ListNode list1 = sortList(head);
    	ListNode list2 = sortList(fast);
    	return mergeList(list1, list2);
    }
    //合並兩鏈表
    public ListNode mergeList(ListNode head1, ListNode head2) {
    	ListNode head = new ListNode(-1);
    	ListNode last = head;
    	while(head1 != null && head2 != null) {
    		if(head1.val <= head2.val) {
    			last.next = head1;
    			head1 = head1.next;
    		} else {
    			last.next = head1;
    			head1 = head1.next;
			}
    		last = last.next;
    	}
    	if(head1 != null)
    		last.next = head1;
    	if(head2 != null)
    		last.next = head2;
    	return head.next;
    }
	
	
	//解法二
//	15 / 15 test cases passed.
//	Status: Accepted
//	Runtime: 709 ms 
//	Submitted: 0 minutes ago
	
	// 對排序好的鏈表設置一個中點指針，如果待排的節點大於中點指針的值，則從中點開始尋找插入點，否則從表頭開始查找
    //其實也沒降低時間復雜度 和暴力插排一樣 仍為O(n*n) 空間復雜度 O(1)
    public ListNode sortList1(ListNode head) {
        ListNode preHead = new ListNode(-1);
        ListNode last = null;
        ListNode cur = null;
        
        int preNum = 0, postNum = 0;
        
        while(head != null) {
        	ListNode headNext = head.next;
        	if(last != null && last.val <= head.val) {
        		postNum ++;
        		cur = last;				
        	} else {
        		preNum ++;
        		cur = preHead;
			}
        	
        	while(cur.next != null) {
				if(cur.next.val >= head.val) {
					break;
				}
				cur = cur.next;
			}
			if(last == null) {
				last = head;
			}
    		ListNode curNext = cur.next;
			cur.next = head;
			cur.next.next = curNext;
        	head = headNext;
        	if(postNum > preNum) {
				last = last.next;
			}
        }
    	return preHead.next;
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}