学步园

LeetCode 上的题目：

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

最初想法是快排，因为要求空间开销O（1），但是某些case无法通过，大家懂得，快排最坏时间开销O（n^2)

所以还是得用merge sort，对于数组merge sort一般需要O（n)空间开销，但是也有in-place merge sort可以做到O(1)空间开销，这个太复杂，

总是记不住。

但是对于链表，做到O（1）空间开销还是相对简单的，只不过要注意一些边界条件。

public ListNode sortList(ListNode head)
	{
		if(head==null||head.next==null)
            return head;

		ListNode tail=head;
		int len=1;
        while(tail.next!=null)
        {
            tail=tail.next;
            len++;
        }
        
        head=mergeSort(null,head,len);
        return head;
	}

	// return the head of sorted list.
	private ListNode mergeSort(ListNode preHead,ListNode head, int len) {

		
		if(head==null||len<=1)
			return head;
		
		int left=len/2;
		int right=len-left;
		//sort left part
		head=mergeSort(preHead,head,left);
		//sort right part
		ListNode pMid=head;
		for(int i=0;i<left-1;i++)
		{
			pMid=pMid.next;
		}
		mergeSort(pMid,pMid.next,right);
		
		//p1 points to left part head,p2 points to right part head
		ListNode p1=head,p2=pMid.next;
		ListNode pre1=preHead,pre2=pMid;
		
		//new head is little one between left head and right head. 
		if(p1.val>p2.val)
			head=p2;
		
		while(left>0&&right>0)
		{
			//if p2.val<p1.val move p2 previous to p1.
			if(p1.val>p2.val)
			{	
				
				//delete p2
				pre2.next=p2.next;
				//add p2 previous to p1
				p2.next=p1;
				if(pre1!=null)
				{
					pre1.next=p2;
				}
				//pre1 move to p2
				pre1=p2;
				//p2 move to pre2.next
				p2=pre2.next;
				right--;
			}
			else
			{
				pre1=p1;
				p1=p1.next;
				left--;
			}
		}
		return head;
	}