【LeetCode】Sort List

Sort a linked list in O(n log n) time using constant space complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode *merge(ListNode *h1, ListNode *h2)
    {
	ListNode *head = new ListNode(0);
	ListNode *p = head;
	while(h1 != NULL && h2 != NULL)
	{
		if(h1->val < h2->val)
		{
			p->next = h1;
			h1 = h1->next;
		}
		else {
			p->next = h2;
			h2 = h2->next;
		}
		p = p->next;
	}
	if(h1 != NULL) 
		p->next = h1;
	else p->next = h2;
	p = head;
	head = head->next;
	delete p;
	return head;
    }

    ListNode *mergeSort(ListNode *head)
    {
	if(head == NULL || head->next == NULL)
		return head;
	ListNode *slow = head;
	ListNode *fast = head;
	ListNode *tail = head;
	while(fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		tail = slow;
		slow = slow->next;
	}	
	tail->next = NULL;
	ListNode *h1 = mergeSort(head);
	ListNode *h2 = mergeSort(slow);
	return merge(h1,h2);
    }
    
    ListNode *sortList(ListNode *head) {
        return mergeSort(head);
    }
};

【LeetCode】Sort List,布布扣,bubuko.com

【LeetCode】Sort List

原文：http://blog.csdn.net/xiaozhuaixifu/article/details/21321051