学步园

【题目描述】Sort a linked list in O(n log n)
time using constant space complexity.

【算法思路】时间复杂度限制在O(n log n)，我们可以第一时间想到常用的二路归并排序，快速排序和堆排序，其中快排和堆排只适用于线性表，即数组，故这道编程题毫无疑问用二路归并排序；

【编程步骤】

 *
1. 利用一个小技巧，可以设置慢行指针low和快行指针fast，把链表分成两部分来操作，即first和second链表
 * 2. 递归排序first和second链表，即

first=sortList(head);
second=sortList(second);
 * 3. 合并这两个链表，即：mergeListSort(first,second)

【代码实现】

/**
 * 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) {
        if(head==null||head.next==null)
			return head;
		ListNode fast=head;
		ListNode slow=head;
		while(fast.next!=null&&fast.next.next != null){
			fast=fast.next.next;
			slow=slow.next;
		}
		ListNode second=slow.next;
		slow.next=null;
		ListNode first=sortList(head);
		second=sortList(second);
		return mergeListSort(first,second);
    }
	private ListNode mergeListSort(ListNode first,ListNode second){
		ListNode newList=new ListNode(0);
		ListNode p=newList;
		while(first!=null&&second!=null){
			if(first.val<=second.val){
				p.next=first;
				first=first.next;
			}else{
				p.next=second;
				second=second.next;
			}
			p=p.next;
		}
		if(first!=null)
			p.next=first;
		if(second!=null)
			p.next=second;
		return newList.next;
	}	
}