Sort List[leetcode] 由歸並排序的遞歸和循環，到本題的兩種解法

Sort List[leetcode] 由歸並排序的遞歸和循環，到本題的兩種解法

歸並排序可以有兩種思路----top-down 和 bottom-up

top-down:

遞歸實現，將數組分成兩半，分別處理；再合並。

偽代碼如下：

split ( A[], l, r)
{
	if ( r - l < 2) return;
	m = (r + l) / 2;
	split ( A, l, m); //split A[l…m-1]
	split ( A, m, r); //split A[m…r-1]
	merge ( A, l, m, e); //merge A[l…m-1] and A[m…e-1]
}

循環實現，將數組看做n個長度為1的組數組。

用width控制每次merge的子數組長度，width每次翻倍

偽代碼如下：

sort ( A[], n)
{
	for (width = 1; width < n; width *= 2)
	{
		for (i = 0; i < n; i += 2 * width)
		{
			merge(A, i, min(i + w, n), min(i + 2 * w, n));
		}
	}
}

和上面的偽代碼類似，首先實現merge函數：

    ListNode * merge(ListNode * h1, int s1, ListNode * h2, int s2)
    {
        if (h2 == NULL) return h1;
        ListNode * h;
        if (h1->val < h2->val)
            h = advance(h1, s1);
        else
            h = advance(h2, s2);
        ListNode * cur = h;
        while (s1 && s2)
        {
            if (h1->val < h2->val)
                cur->next = advance(h1, s1);
            else
                cur->next = advance(h2, s2);
            cur = cur->next;
        }
        if (s1)
        {
            cur->next = h1;
            while(s1) advance(h1, s1);
        }
        if (s2)
        {
            cur->next = h2;
            while(s2) advance(h2, s2);
        }
        return h;
    }
    
    ListNode * advance(ListNode * (& n), int & size)
    {
        ListNode * temp = n;
        if (size == 1)  n->next = NULL;
        n = n->next;
        size--;
        return temp;
    }

同時實現工具函數，訪問任意位置節點

ListNode * getNode(ListNode * head, int len)
    {
        while (len -- && head) head = head->next;
        return head;
    }

ListNode *sortList(ListNode *head) {
        ListNode * cur = head;
        int size = 0;
        while (cur)
        {
            size ++;
            cur = cur->next;
        }
        
        ListNode * pre;
        for (int w = 1; w <= size; w *= 2)
        {
            cur = head;
            for (int i = 0; i < size; i+= w*2)
            {
                ListNode * h1 = cur, * h2 = getNode(cur, w), * next = getNode(cur, 2 * w);
                cur = merge(h1, min(w, size - i), h2, min(w, size - i - w));
                if (i == 0)     
                    head = cur;
                else            
                    pre->next = cur;
                pre = getNode(cur, min(2 * w, size - i) - 1);
                cur = next;
            }
        }
        return head;
    }

    ListNode *sortList(ListNode *head) {
        ListNode * cur = head;
        int size = 0;
        while (cur)
        {
            size ++;
            cur = cur->next;
        }
        return sort(head, size - size / 2, getNode(head, size - size / 2), size / 2);
    }
    
    ListNode * sort(ListNode * h1, int s1, ListNode * h2, int s2)
    {
        if (s1 == 0) return h2;
        if (s2 == 0) return h1;
        h1 = sort(h1, s1 - s1 / 2, getNode(h1, s1 - s1 / 2), s1 / 2);
        h2 = sort(h2, s2 - s2 / 2, getNode(h2, s2 - s2 / 2), s2 / 2);
        return merge(h1, s1, h2, s2);
    }