c++ merge sort solution

• Here is my merge sort solution, using two pointers to find the middle of linked list, and merge two lists using ListNode* tail.

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* left, ListNode* right){
if(!left && !right) return NULL;
else if(!left && right) return right;
else if(!right && left) return left;

ListNode* tail;
if(left->val < right->val) {
left = left->next;
}
else {
right = right->next;
}

while(left && right){
if(left->val <= right->val) {
tail->next = left;
left = left->next;
}
else {
tail->next = right;
right = right->next;
}
tail = tail->next;
}
if(left && !right) tail->next = left;
else if(!left && right) tail->next = right;
}

while(fast && fast->next){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}

// only one node in list
// only two nodes in list
else if(!slow->next){
else{
pre->next = NULL;
slow->next = pre;
return slow;
}
}

pre->next = NULL;