merge sort in linkedlist wrong answer
problem- https://www.interviewbit.com/problems/sort-list/
ListNode* merge(ListNode* A, ListNode* B) {
ListNode *p=A,*q=B,*r,*ans;
int k=0;
while(p && q)
{
if(k==0)
{
if(p->valval)
{
r=p;
p=p->next;
k=1;
}
else
{
r=q;
q=q->next;
k=1;
}
ans=r;
}
else
{
if(p->valval)
{
r->next=p;
p=p->next;
}
else
{
r->next=q;
q=q->next;
}
}
}
if(!p && !q)
r->next=NULL;
else if§
r->next=p;
else if(q)
r->next=q;
return ans;
}
ListNode* Solution::sortList(ListNode* A) {
if(!A )
return NULL;
if(!A->next)
return A;
ListNode *sp=A,*fp=A->next;
while(fp && fp->next)
{
sp=sp->next;
fp=fp->next->next;
}
ListNode *t=sp->next;
sp->next=NULL;
A=sortList(A);
t=sortList(t);
ListNode *ans=merge(A,t);
return ans;
}