学步园

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

参考：http://blog.csdn.net/magisu/article/details/16814915

原先虽然我也写出了大部分，调试通过，但是提交一直是Time Limit Exceeded，后来怀疑是java链表效率低，用cpp也实现了一下依然一样。。

看了上面那博主的文章后，我发现有一点我没有考虑到，就是当参考值相同的时候，应该将值放到参考值链表中，减少了大量重复排序工作，也为自己积累了经验，这个是我LeetCode第三题，花了将近2天时间，希望以后能越来越快

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
	public ListNode sortList( ListNode head )
	{
		LinkList result = QuickSort( head );
		return result == null ? null : result.head;
	}
	public LinkList QuickSort( ListNode head )
	{
		if( head == null) return null;
		int standValue = head.val;
		ListNode p = head.next;
		LinkList lstand = new LinkList();
		lstand.appendAndBreak( head );
		LinkList lleft = new LinkList();
		LinkList lright = new LinkList();
		while( p != null )
		{
			ListNode next = p.next;
			if( p.val < standValue ) lleft.appendAndBreak(p);
			else if( p.val == standValue)  lstand.appendAndBreak(p);
			else lright.appendAndBreak(p);
			p = next;
		}
		if( lleft.size > 1 ) lleft = QuickSort( lleft.head );
		if( lright.size > 1 ) lright = QuickSort( lright.head );
		return lleft.merge(lstand).merge(lright);
	}
}


class LinkList
{
	ListNode head;
	ListNode last;
	int size = 0;
	public void appendAndBreak( ListNode node )
	{
		if( head == null )
		{
			this.head = node;
			this.last = node;
			size = head == null ? 0:1;
		}
		else
		{
			this.last.next = node;
			this.last = node;
			size ++;
		}
		node.next = null;
	}
	public LinkList merge( LinkList k )
	{
		if( size == 0 ) 
			return k;
		else
		{
			if( k.size == 0 ) return this;
			else
			{
				this.last.next = k.head;
				this.last = k.last;
				this.size += k.size;
			}
		}
		return this;
	}
}