# Two different solutions well-commented in C accepted as best

• ``````//AC - 20ms;
struct ListNode* merge(struct ListNode* l, struct ListNode* r)
{
while(l && r)
{
if(l->val <= r->val) //collect left first when left and right are equal;
{
p->next = l;
l = l->next;
}
else
{
p->next = r;
r = r->next;
}
p = p->next;
}
p->next = (l == NULL ? r : l);
}
{
while(s2 && s2->next) //split the list into two halves;
{
s1 = s1->next;
s2 = s2->next->next;
}
s2 = s1->next;
s1->next = NULL;
return merge(sortList(head), sortList(s2)); //merge two parts by invoking recursive method;
}
``````

``````struct ListNode* partition(struct ListNode* head, struct ListNode* tail)
{
struct ListNode left, mid, right; //the head of each position;
struct ListNode *l=&left, *m=&mid, *r=&right; //used to move forward;
{
{
l = l->next;
}
{
r = r->next;
}
else
{
m = m->next;
}
}
r->next = tail; //connect the right end to the next part;
m->next = partition(right.next, tail);  //connect the middle part to the right;
l->next = mid.next; //connect the left to the middle;
return partition(left.next, l->next); //handle the left part and return the head of the left;
}

//AC - 16ms;
{
}``````

• @LHearen Both are recursive. Neither satifies the "constant space complexity" requirement.

• @ayuanx You are `almost` right about that. But to make the code simple to avoid `bottom-up` method, here I'd prefer to use `top-down` one. Of course, thank you for your pointing it out.

• @LHearen Why "almost" right? They're just right.

• @LHearen If the problem doesn't say "must use constant space", then your solutions are all good.
But in interview, if the interviewer says "must use constant space", your recursive solution will get 0 point. Yeah I know it is fussy, but interviewers are like gods in such scenarios.

• @StefanPochmann Yes, you're right about this. Sorry for the word used in the previous post. I will try to make up another version to solve this problem A.S.A.P. Thank you, guys!

• @LHearen I am not against anybody. Yes I am aware that my words could be misleading sometimes. That's because it is my habit to say it when I see it in the first place.

• @ayuanx It's fine, buddy. You're `efficient` type caring about the result. Huhhuh, nice to have you in Leetcode. Have fun!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.