# Combination of Merge2List & 2-Pointers

• ``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(tail && tail->next)  { mid=mid->next; tail=tail->next->next; }
mid->next=NULL;
ListNode* sort_left=sortList(left);
ListNode* sort_right=sortList(right);
return help(sort_left, sort_right);
}

ListNode* help(ListNode* left, ListNode* right){
ListNode* result=new ListNode(-1);
ListNode* cur=result;
while(left && right){
if(left->val<=right->val) {
cur->next=left;  left=left->next;
}else{
cur->next=right; right=right->next;
}
cur=cur->next;
}
if(left)    cur->next=left;
if(right)   cur->next=right;
return result->next;
}
};``````

• First check the special cases : NULL or SingleNode

The merge function should be carefully implemented ...

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/** bugs here */

ListNode* dummy = new ListNode(INT_MIN);
ListNode* slow = dummy, * fast = dummy;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

ListNode* right_half = slow->next;
slow->next = NULL;

ListNode* left = sortList(dummy->next);
ListNode* right = sortList(right_half);

return mergeList(left, right);
}

ListNode* mergeList(ListNode* left, ListNode* right) {
ListNode* dummy = new ListNode(INT_MIN);
ListNode* cur = dummy;
while(left && right) {
if(left->val < right->val) {
cur->next = left;
left = left->next;
}
else {
cur->next = right;
right = right->next;
}
/** bugs here */
cur = cur->next;
}
if(left)  cur->next = left;
if(right) cur->next = right;
return dummy->next;
}
};``````

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