算法详解——链表的归并排序非递归解法

算法详解——链表的归并排序非递归解法

本文使用倍增法加上归并排序操作实现了对链表的快速排序，比起一般的递归式归并排序要节省空间并且实现要简单的多，比起一般的迭代式归并排序实现也要简单。

1. 题目假设

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

要实现对该链表的快速排序（时间复杂度达到O(nlogn)），比较合适的选择是归并排序（当然快速排序也不是不行）。

## 2. 回顾一般的解法

一般的解法主要有两种形式，即自顶向下法和自底向上法，前者使用递归实现，后者使用迭代实现。

自定向下——递归法

算法思想如下：

1. 如果当前链表为空或者只有一个结点，直接返回该链表
2. 找到该链表的中间结点（可以使用快慢指针）
3. 对左右两条子链执行递归，得到两条排好序的子链
4. 对两条子链进行归并排序，得到一个有序链表，返回其头指针

自底向上——迭代法

算法思想如下：

1. 设置步长step为1
2. 以step个结点为一条子链，从头节点开始遍历，每凑够两条子链，就执行归并操作。如果结点总数小于等于step，直接返回。
3. 倍增step

但两种方法对于数组来说是比较合适的，因为数组可以随机访问，这样可以很方便的找到中点或者找到下一个长度为step的数组。但是对于链表来说实现起来就比较复杂。

3. 倍增法归并排序

倍增法归并排序的思想是这样的，想象一个64位的整数，那么整数中的第i位能够代表2的i次方的值。

当执行加1操作时，将会从第0位开始如果是0就变为1并返回，如果是1就变为0并继续向后操作。

受此启发，我们可以建立一个64位大小的链表数组，然后遍历待排序链表的每个结点，将其“加入”链表数组。

加入的方法为：从数组的左边开始遍历，如果该位为空就直接加入并返回，如果不为空就执行归并操作并将该位置为空，然后继续向后操作。

详细操作步骤请看代码和注释。代码如下：

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 创建大小为64的链表指针数组
        ListNode *A[64] = {0};

        // 遍历待排序链表的每个结点并将其加入指针数组
        auto it = head;
        while (it != nullptr)
        {
            // 取下当前头节点，并赋值给cur
            auto cur = it;
            it = it->next;
            cur->next = nullptr;

    // 遍历指针数组
            for (int i = 0; i < 64; ++i)
            {
                // 如果当前数组元素为空（对应整数加法中当前位为0），则将其置为当前链表cur
                if (A[i] == nullptr)
                {
                    A[i] = cur;
                    break;
                }
                else// 否则将cur与当前数组元素所指链表执行归并操作，并将得到的新链表赋给cur，然后将数组元素置空（想想对应加法操作中的什么）
                {
                    cur = merge(cur, A[i]);
                    A[i] = nullptr;
                }
            }
        }

        // 最后将指针数组中的所有链表都从左到右进行归并操作，得到一个完整的排好序的链表
        ListNode *res = nullptr;
        for (int i = 0; i < 64; ++i)
        {
            if (A[i] != nullptr)
            {
                res = merge(res, A[i]);
            }
        }
        return res;
    }

    // 对left和right两条链表进行归并排序
    ListNode *merge(ListNode *left, ListNode *right)
    {
        ListNode dummy_node;// 伪头结点
        ListNode *tar = &dummy_node;

        while (left != nullptr & right != nullptr)
        {
            if (left->val < right->val)
            {
                tar->next = left;
                left = left->next;
            }
            else
            {
                tar->next = right;
                right = right->next;
            }
            tar = tar->next;
        }
        if (left) tar->next = left;
        if (right) tar->next = right;
        return dummy_node.next;
    }
};

4. 复杂度分析

空间复杂度

首先分析空间复杂度，可以看到全程只是建立了一个大小为64的指针数组以及归并排序过程中创建了一个伪头节点，因此空间复杂度为O(1)。

时间复杂度

时间复杂度的分析就稍有些复杂，不妨从指针数组中每层发生的归并的次数来看：

在数组第0位上，需要进行n/2次归并得到n/2条的结点数为2的有序链表；在数组第1位上，需要进行n/4次归并，得到n/4条结点数位4的有序链表，依次类推。

在每层的归并操作中，执行比较总次数都是O(n)，而总层数可以用O(logn)表示，因此总的时间复杂度就是O(nlogn)。

学习参考

学习更多相关知识请参考零声 github。

原文地址：https://blog.csdn.net/leedcanDD/article/details/143598401

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！