Sort a linked list in O(n log n) time using constant space complexity.
分析：题目要求时间复杂度为O(nlogn)，所以不能用quickSort（最坏O(n^2)），可以使用mergeSort.
对一个链表进行归并排序，首先注意归并排序的基本思想：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge。
而找到链表中间点可以利用快慢指针的思想：用两个指针，一个每次走两步，一个走一步，知道快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两个链表。
merge时，把两段头部节点值比较，用一个 p 指向较小的，且记录第一个节点，然后 两段的头一步一步向后走，p也一直向后走，总是指向较小节点，直至其中一个头为NULL，处理剩下的元素，最后返回记录的头节点即可。
code如下：
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(!head||!head->next)
return head;
return mergeSort(head);
}
ListNode * mergeSort(ListNode *head){
if(!head||!head->next) //just one element
return head;
ListNode *p=head, *q=head, *pre=NULL;
while(q&&q->next!=NULL){
q=q->next->next;
pre=p;
p=p->next; //divide into two parts
}
pre->next=NULL;
ListNode *lhalf=mergeSort(head);
ListNode *rhalf=mergeSort(p); //recursive
return merge(lhalf, rhalf); //merge
}
ListNode * merge(ListNode *lh, ListNode *rh){
ListNode *temp=new ListNode(0);
ListNode *p=temp;
while(lh&&rh){
if(lh->val<=rh->val){
p->next=lh;
lh=lh->next;
}
else{
p->next=rh;
rh=rh->next;
}
p=p->next;
}
if(!lh)
p->next=rh;
else
p->next=lh;
p=temp->next;
temp->next=NULL;
delete temp;
return p;
}
};
python：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
if not head or not head.next:
return head
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
rlist = self.sortList(slow.next)
slow.next = None
llist = self.sortList(head)
return self.mergeList(llist, rlist)
def mergeList(self, l1, l2):
nHead = ListNode(0)
lastnode = nHead
while l1 and l2:
if l1.val < l2.val:
lastnode.next = l1
l1 = l1.next
else:
lastnode.next = l2
l2 = l2.next
lastnode = lastnode.next
lastnode.next = l1 or l2
return nHead.next
Python语言是一款对缩进非常敏感的语言，在编译时会出现这样的错IndentationError:expected an indented block说明此处需要缩进，你只要在出现错误的那一行，按空格或Tab（但不能混用）键缩进就行。 ----（有冒号的下一行往往要缩进，该缩进就缩进）
ps：标记部分若set fast = head, the code will be beyond the time. The difference of the two situations are as follows:
