Merge sort on linked list

How to apply Merge Sort to linked list?

• for more about Merge Sort, please refer to Merge Sort.
• Merge Sort works better on linked list than it does on arrays, in the sense of constant auxiliary space complexity.

A simple implementation in C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
public:
    // merge sort linked list
    ListNode* sortlist(ListNode* head){
        if(head != NULL)
            return mergeSort(head);
        return head;   
    }

    ListNode* mergeSort(ListNode* node){
        if(node->next != NULL){
            ListNode* firstHalf = node;
            ListNode* secondHalf = mergeSplit(node);
            firstHalf = mergeSort(firstHalf);
            secondHalf = mergeSort(secondHalf);
            ListNode* result = sortedMerge(firstHalf, secondHalf);
            return result;
        }
        return node;
    }

    // find the first&second half of the list
    ListNode* mergeSplit(ListNode* node){
        ListNode* secondHalf;
        ListNode* stepOne = node;
        ListNode* stepTwo = node->next;
        while(stepTwo != NULL && stepTwo->next != NULL){
            stepTwo = stepTwo->next;
            stepTwo = stepTwo->next;
            stepOne = stepOne->next;           
        }  
        secondHalf = stepOne->next;
        stepOne->next = NULL;
        return secondHalf;
    }

    // merge the sorted list
    ListNode* sortedMerge(ListNode* firstHalf, ListNode* secondHalf){
        //step1 - swap the new header
        //step2 - link the list
        ListNode* tmpf = firstHalf;
        ListNode* tmps = secondHalf;
        ListNode* tmp = new ListNode(99);
        ListNode* tmpHead = tmp;
        while(tmpf != NULL && tmps!= NULL){
            if(tmpf->val <= tmps->val){
                tmp->next = tmpf;
                tmp = tmp->next;
                tmpf = tmpf->next;
            }
            else{
                tmp->next = tmps;
                tmp = tmp->next;
                tmps = tmps->next;
            }
        }
        if(tmpf == NULL)
            tmp->next = tmps;
        if(tmps == NULL)
            tmp->next = tmpf;          
        return tmpHead->next;
    }
};