Sort List

解题思路

  1. 链表排序的经典实现就是归并排序；

  2. sgi-stl 使用 Bottom-Up 的迭代写法，clang 使用 Top-Down 的递归写法，下面是不太好理解的迭代式代码。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* carry;
        vector<ListNode*> counter(64, nullptr);
        int fill = 0;
        while(head != nullptr) {
            carry = head;
            head = head->next;
            carry->next = nullptr;
            int i = 0;
            while (i < fill && counter[i] != nullptr) {
                carry = merge(carry, counter[i]);
                counter[i] = nullptr;
                ++i;
            }
            swap(counter[i], carry);
            if (i == fill) {
                fill++;
            }
        }
        for (int i = 1; i < fill; ++i) {
            counter[i] = merge(counter[i], counter[i-1]);
        }
        return counter[fill-1];
    }
    
    ListNode* merge(ListNode* ListA, ListNode* ListB) {
        ListNode dummy(-1);
        ListNode* head = &dummy;
        while (ListA && ListB) {
            if (ListA->val < ListB->val) {
                head->next = ListA;
                ListA = ListA->next;
            } else {
                head->next = ListB;
                ListB = ListB->next;
            }
            head = head->next;
        }
        if (ListA) {
            head->next = ListA;
        } else {
            head->next = ListB;
        }
        return dummy.next;
    }
};