C++ solution, 74 ms


  • 0
    X
    class Solution
    {
    public:
    	ListNode* merge(ListNode* first, ListNode* second)
    	{
    		if(NULL == first && NULL == second)
    			return NULL;
    
    		ListNode* res = NULL;
    		ListNode* cursor = NULL;
    		ListNode* p = NULL;
    
    		while(NULL != first && NULL != second)
    		{
    			if(first->val < second->val)
    			{
    				p = first;
    				first = first->next;
    			}
    			else
    			{
    				p = second;
    				second = second->next;
    			}
    
    			if(NULL == res)
    			{
    				res = p;
    				cursor = p;
    			}
    			else
    			{
    				cursor->next = p;
    				cursor = p;
    			}
    		}
    
    		p = NULL;
    		if(NULL != first)
    		{
    			p = first;
    		}
    		if(NULL != second)
    		{
    			p = second;
    		}
    		if(NULL == res)
    		{
    			res = p;
    		}
    		else
    		{
    			cursor->next = p;
    		}
    		return res;
    	}
    
    	void concatenate(ListNode* & first, ListNode* & second, ListNode* & cursor)
    	{
    		if(NULL != first)
    		{
    			cursor->next = second;
    		}
    		else
    		{
    			first = second;
    			cursor = second;
    		}
    
    		while(NULL != cursor->next)
    		{
    			cursor = cursor->next;
    		}
    	}
    
    	ListNode* sortList(ListNode* head)
    	{
    		int len = 0;
    		ListNode* ptr = NULL;
    		ListNode* first = NULL;
    		ListNode* second = NULL;
    		ListNode* cursor = NULL;
    		ListNode* p = NULL;
    		ptr = head;
    		while(NULL != ptr)
    		{
    			++len;
    			ptr = ptr->next;
    		}
    
    		int count = 1;
    		while(count < len)
    		{
    			ptr = head;
    			head = NULL;
    			cursor = NULL;
    
    			while(NULL != ptr)
    			{
    				first = NULL;
    				second = NULL;
    
    				first = ptr;
    				for(int i = 0; i < count - 1 && NULL != ptr; ++i)
    				{
    					ptr = ptr->next;
    				}
    
    				if(NULL != ptr)
    				{
    					second = ptr->next;
    					ptr->next = NULL;
    					ptr = second;
    				}
    
    				for(int i = 0; i < count - 1 && NULL != ptr; ++i)
    				{
    					ptr = ptr->next;
    				}
    
    				if(NULL != ptr)
    				{
    					p = ptr->next;
    					ptr->next = NULL;
    					ptr = p;
    				}
    
    				p = merge(first, second);
    				concatenate(head, p, cursor);
    			}
    			count *= 2;
    		}
    		return head;
    	}
    };

Log in to reply
 

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