leetcode148：排序链表

题目链接

leetcode

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    自顶向下归并排序

    1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。
        寻找链表的中点：用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步。
        当快指针到达链表末尾时，慢指针指向的链表结点即为链表的中点。
    2.对两个子链表分别排序。
    3.将两个排序后的子链表合并，得到完整的排序后的链表。
        使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
    上述过程可以通过递归实现。递归的终止条件是链表的结点个数小于或等于 1。

    时间复杂度：O(nlogn)
        其中 n 是链表的结点个数
    空间复杂度：O(logn)
        在最坏情况下，递归调用的栈深度为 logn
*/
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr) {
            return head;
        }
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }

        ListNode* mid = getMidNode(head, tail);
        return merge(sortList(head, mid), sortList(mid, tail));
    }

    ListNode* getMidNode(ListNode* head, ListNode* tail) {
        ListNode* slow = head, *fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
        
        return slow;
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(), *p = dummy;
        ListNode *p1 = l1, *p2 = l2;

        while (p1 && p2) {
            if (p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = (p1 ? p1 : p2);

        return dummy->next;
    }
};

/*
    自底向上归并排序

    首先求得链表的长度，然后将链表拆分成子链表进行合并。
    1.step 表示每次需要排序的子链表的长度，初始时 step = 1。
    2.每次将链表拆分成若干个长度为 step 的子链表（最后一个子链表的长度可以小于 Length）
        按照两个子链表一组进行合并，合并后得到若干个长度为 step*2 的有序子链表。
        合并两个子链表仍然使用「21. 合并两个有序链表」的做法。
    3.将 step 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，
        直到有序子链表的长度大于或等于 length，整个链表排序完毕。

    如何保证每次合并之后得到的子链表都是有序的呢？
    可以通过数学归纳法证明。因此，保证最后得到的链表是有序的。

    时间复杂度：O(nlog⁡n)
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }

        // 统计链表长度
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }

        ListNode* dummy = new ListNode(-1, head);
        // 逐步翻倍 step
        for (int step = 1; step < length; step <<= 1) {
            // 遍历当前链表进行合并
            ListNode *prev = dummy, *cur = dummy->next;
            
            while (cur != nullptr) {
                // 分割两个子链表
                ListNode* head1 = cur;
                for (int i = 1; i < step && cur->next != nullptr; i++) {
                    cur = cur->next;
                }

                ListNode* head2 = cur->next;
                cur->next = nullptr; // 断开第一个子链表
                cur = head2;
                for (int i = 1; i < step && cur != nullptr && cur->next != nullptr; i++) {
                    cur = cur->next;
                }

                ListNode* next = nullptr;
                if (cur != nullptr) {
                    next = cur->next;
                    cur->next = nullptr; // 断开第二个子链表
                }
                
                // 合并两个子链表
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                cur = next;
            }
        }
        
        return dummy->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummy = new ListNode();
        ListNode *cur = dummy, *l1 = head1, *l2 = head2;
        
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1 != nullptr) {
            cur->next = l1;
        } else if (l2 != nullptr) {
            cur->next = l2;
        }

        return dummy->next;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> head_cases = {
        {4,2,1,3},
        {-1,5,3,4,0},
        {}
    };

    for (size_t i = 0; i < head_cases.size(); i++) {
        // 创建链表
        ListNode* head = createList(head_cases[i]);
        cout << "Input: ";
        printList(head);

        // 排序操作
        ListNode* result = solution.sortList(head);
        cout << "Output: ";
        printList(result);

        // 释放内存
        deleteList(result);
    }

    return 0;
}