[LeetCode 148] Sort List

题目链接：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

	}

}

[LeetCode 148] Sort List

原文：http://blog.csdn.net/ever223/article/details/44644821