Sort a linked list in O(n log n)
time using constant space complexity.
1.链表的排序一般每遇到过，让用O(nlogn)解决该问题就更不知如何下手了
2.通过参考网上的思路才知道用归并排序，采用递归的方法解决该问题还是可以的，就是理解起来有点费劲
3.重要步骤：递归，归并，查找数组有效范围内的中间节点，有序数组合并
public ListNode sortList(ListNode head)
{
if(head==null||head.next==null)
return head;
ListNode midNode=getMidNode(head);
ListNode newHead=midNode.next;
midNode.next=null;
head=mergeLists(sortList(newHead), sortList(head));
return head;
}
public ListNode mergeLists(ListNode head1, ListNode head2)
{
if(head1==null&&head2==null)
return head1;
if(head1==null)
return head2;
if(head2==null)
return head1;
ListNode newHead=new ListNode(-1);
ListNode curListNode=newHead;
while(head1!=null&&head2!=null)
{
if(head1.val<head2.val)
{
curListNode.next=head1;
head1=head1.next;
}else
{
curListNode.next=head2;
head2=head2.next;
}
curListNode=curListNode.next;
}
if(head1!=null)curListNode.next=head1;
if(head2!=null)curListNode.next=head2;
return newHead.next;
}
public ListNode getMidNode(ListNode head)
{
if(head==null||head.next==null)
return head;
ListNode p=head,q=head;
while(q.next!=null&&q.next.next!=null)
{
p=p.next;
q=q.next.next;
}
return p;
}版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/mnmlist/article/details/47440479