[LeetCode] Sort List

Link : http://oj.leetcode.com/problems/sort-list/
Sort a linked list in O(n log n) time using constant space complexity.

iterative version of merge sort.
Code is ugly and needs substantial modification.

class Solution {
    public:
    
    ListNode *sortList(ListNode *head) {
        if(!head) return NULL;
        ListNode dummy(0);
        dummy.next = head;
        // get length
        int n=0;
        ListNode* cursor=&dummy;
        ListNode* tmp;
        while(cursor->next) { n++; cursor=cursor->next; }
        
        ListNode* current_first=head;
        ListNode* next_first=NULL;
        
        ListNode* merge_head=NULL;
        ListNode* merge_tail=NULL;
        
        // scan using different step
        for(int step=1; step<n; step*=2)
        {
            // initialization
            cursor = &dummy;
            current_first = dummy.next;
            // for each step, merge two adjacent sub lists
            for(int i=0; i<n; i+=step*2)
            {
                next_first = moveNode(current_first, step*2-1);
                if(next_first) // cut link between different sub list
                {
                    tmp = next_first->next;
                    next_first->next = NULL;
                    next_first = tmp;
                }
                merge(current_first, step, merge_head, merge_tail);
                cursor->next = merge_head; // concatenation
                cursor = merge_tail; // ready for next concatenation
                current_first = next_first; // ready for next merge
            }
        }
        return dummy.next;
    }
    
    ListNode* moveNode(ListNode* p, int step)
    {
        while(step-->0&&p) p=p->next;
        return p;
    }
    
    void merge(ListNode* head, int step, ListNode*& merge_head, ListNode*& merge_tail)
    {
        if(head==NULL) return;
        ListNode dummy(0);
        ListNode* tmp;
        
        ListNode* cursor = &dummy;
        ListNode* l1 = head;
        // get second sub-list
        ListNode* l2 = head;
        // get the node pointing to the head of second sub-list
        l2 = moveNode(l2, step-1);
        if(l2) // cut link between different sub list
        {
            tmp = l2->next;
            l2->next = NULL;
            l2 = tmp;
        }
        
        while(l1||l2)
        {
            if((l1&&!l2)||(l1&&l2&& l1->val <= l2->val))
            {
                tmp = l1->next;
                l1->next=NULL;
                cursor->next = l1;
                
                l1=tmp;
                cursor=cursor->next;
            }
            else
            {
                tmp = l2->next;
                l2->next=NULL;
                cursor->next = l2;
                
                l2=tmp;
                cursor=cursor->next;
            }
        }
        merge_head = dummy.next;
        merge_tail = cursor;
    }
    
};