Sort a linked list in O(n log n) time using constant space complexity.
逻辑正确，尾指针没有置空，调了好久……
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(head == NULL)return head;
ListNode *temp = head;
int n =0;
while(temp!=NULL)
{
n++;
temp = temp->next;
}
head =merge(head,n);
return head;
}
ListNode *merge(ListNode *head, int n)
{
if(n>2)
{
ListNode * temp =head;
ListNode * first;
ListNode * second;
ListNode * tail = NULL;
int mid = (1+n)/2;
for(int i = 0; i < mid ; i++)temp =temp->next;
first = merge(head,mid);
second = merge(temp,n-mid);
//for(int i = mid; i < n ; i++)temp =temp->next;
tail = temp->next;
ListNode *ft =first;
ListNode *st =second;
ListNode *me = new ListNode(0);
temp =me;
while(ft!= NULL && st!= NULL)
{
if(ft->val < st->val)
{
temp->next =ft;
temp = temp->next;
ft=ft->next;
temp->next =NULL;
}
else
{
temp->next =st;
temp = temp->next;
st=st->next;
temp->next =NULL;
}
}
if(ft!=NULL)
{
temp->next = ft;
//while(ft->next!=NULL)ft =ft->next;
//ft->next = tail;
}
else if(st!=NULL)
{
temp->next = st;
//while(st->next!=NULL)st =st->next;
//st->next = tail;
}
return me->next;
}
else if(n == 2)
{
if(head->val > head->next->val )
{
ListNode * temp =head;
ListNode * second = head->next;
temp->next = NULL;
head = second;
//temp->next = second->next;
head->next =temp;
return head;
}
else
{
head->next->next=NULL;
return head;
}
}
else if(n == 1)
{
head->next =NULL;
return head;
}
}
ListNode * sortl(ListNode *head , int n)
{
if(n<2)return head;
ListNode * temp;
ListNode * left =new ListNode(0);
ListNode * lt = left;
ListNode * right = new ListNode(0);
ListNode * rt = right;
ListNode * mid;
mid = head;
int va = mid->val;
int ln = 0, rn = 0;
temp = head->next;
for(int i =1 ; i < n-1 ; i++)
{
if(temp->val <= va)
{
lt->next = temp;
lt =lt->next;
temp =temp->next;
ln++;
}
else
{
rt->next = temp;
rt = rt->next;
temp =temp->next;
rn++;
}
}
ListNode * tail = temp->next;
if(temp->val <= va)
{
lt->next = temp;
lt =lt->next;
ln++;
}
else
{
rt->next = temp;
rt = rt->next;
rn++;
}
if(ln >0)
{
lt->next = mid;
head = sortl(left->next,ln);
}
else
head = mid;
if(rn>0)
{
rt->next =tail;
mid ->next= sortl(right->next,rn);
}
else
mid->next=tail;
return head;
}
};