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

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

1. 题目假设

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

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

## 2. 回顾一般的解法

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

自定向下——递归法

算法思想如下：

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

自底向上——迭代法

算法思想如下：

设置步长step为1
以step个结点为一条子链，从头节点开始遍历，每凑够两条子链，就执行归并操作。如果结点总数小于等于step，直接返回。
倍增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){// 取下当前头节点，并赋值给curauto cur = it;it = it->next;cur->next = nullptr;// 遍历指针数组for (int i = 0; i < 64; ++i){// 如果当前数组元素为空（对应整数加法中当前位为0），则将其置为当前链表curif (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;}
};