归并排序 - 排序链表 - 《数据结构与算法》

题目
解法一：快排
- 思路分析
解法二：归并排序
- 思路分析

题目

题目来源：力扣（LeetCode）

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

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

解法一：快排

思路分析

快速排序可以通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

借鉴快排的思想，我们可以选取头节点作为分界值，然后遍历链表，如果是比分界值小的节点则将它插在分界值的前面，如果是比分界值大的节点，则将它插在分界值的后面。

假设lhead维护的是小于基准值的头插指针，utail维护的是大于等于基准值的尾插指针，则一次对[head , end）快排结束后有：

[ lhead , head ) （左闭右开）是小于基准值的一部分
[ head.next , end ) （左闭右开）是大于等于基准值的一部分

再分治这两部分即可

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
  return quickSort(head, null);
};
function quickSort(head, end) {
  if (head == end || head.next == end) return head;
  let lhead = head;
  let utail = head;
  let p = head.next;
  while(p != end) {
    let next = p.next;
    if (p.val < head.val) {
      // 当前遍历的节点值小于分界值，将当前遍历的节点插在分界值的前面
      p.next = lhead;
      lhead = p;
    } else {
      // 当前遍历的节点值大于分界值，将当前遍历的节点插在分界值的后面
      utail.next = p;
      utail = p;
    }
    p = next;
  }
  utail.next = end;
  // 对小于分界值的一部分继续遍历排序
  let node = quickSort(lhead, head);
  // 对大于分界值的一部分继续遍历排序
  head.next = quickSort(head.next, end);
  return node;
}

解法二：归并排序

思路分析

时间复杂度是 O(n log n) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n²)），其中最适合链表的排序算法是归并排序。

归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(logn)。如果要达到O(1) 的空间复杂度，则需要使用自底向上的实现方式。

方法一：自顶向下归并排序 (递归)

对链表自顶向下归并排序的过程如下：

找到链表的中点，以中点为分界，将链表拆分成两个子链表。奇数个节点找到中点，偶数个节点找到中心左边的节点。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并，得到完整的排序后的链表。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
  return toSortList(head, null)
};
// 合并两个有序链表
const merge = (head1, head2) => {
  const dummyHead = new ListNode(0); // 创建一个虚拟头节点
  let temp = dummyHead, temp1 = head1, temp2 = head2;
  while (temp1 !== null && temp2 !== null) {
    if (temp1.val <= temp2.val) {
      temp.next = temp1;
      temp1 = temp1.next;
    } else {
      temp.next = temp2;
      temp2 = temp2.next;
    }
    temp = temp.next
  }
  // 比较哪个链表还有没被比较完的值，直接把temp指针指向他
  if (temp1 !== null) {
    temp.next = temp1
  } else if (temp2 !== null) {
    temp.next = temp2
  }
  // 返回排序好的链表头
  return dummyHead.next;
}
const toSortList = (head, tail) => {
  if (head === null) return head;
  if (head.next === tail) {
    head.next = null;
    return head;
  }
  let slow = head, fast = head;
  // 快慢指针找到链表中点
  // 慢指针 slow 走一步
  // 快指针 fast 走两步
  while (fast !== tail) {
    slow = slow.next;
    fast = fast.next;
    if (fast !== tail) {
      fast = fast.next;
    }
  }
  // 当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点
  const mid = slow; 
  return merge(toSortList(head, mid), toSortList(mid, tail))
}

方法二：自底向上归并排序 (迭代)

使用自底向上的方法实现归并排序，则可以达到 O(1)O(1) 的空间复杂度。
首先求得链表的长度 length，然后将链表拆分成子链表进行合并。

具体做法如下:

用 subLength 表示每次需要排序的子链表的长度，初始时 subLength = 1 。
每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength × 2 的有序子链表（最后一个子链表的长度可以小于subLength × 2）。
将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。 ```javascript /**
- Definition for singly-linked list.
- function ListNode(val, next) {
- this.val = (val===undefined ? 0 : val)
- this.next = (next===undefined ? null : next)
- } / /*
- @param {ListNode} head
- @return {ListNode} */

var sortList = function(head) { if (head === null) { return head; } // 获取链表的长度 let length = getLength(head) // 创建一个虚拟头节点 const dummyHead = new ListNode(0, head); // 迭代链表 // <<= 左移赋值运算符 subLength <<= 1 相当于是 subLength *= 2 左移一位，相当于是乘以 2 for (let subLength = 1; subLength < length; subLength <<= 1) { // 每次变化步长，prev 指针和 curr 指针都初始化在链表头 let prev = dummyHead, curr = dummyHead.next; while (curr !== null) {

  // 第一部分链表
  let head1 = curr;
  for (let i = 1; i < subLength && curr.next !== null; i++) {
    curr = curr.next;
  }
  // 第二部分链表
  let head2 = curr.next;
  curr.next = null; // 切断连接
  curr = head2; // 将 curr 变为第二部分链表头
  for (let i = 1; i < subLength && curr != null && curr.next !== null; i++) {
    curr = curr.next;
  }
  let next = null;
  if (curr !== null) {
    next = curr.next;
    curr.next = null;
  }
  // 将一二部分排序合并
  const merged = merge(head1, head2);
  prev.next = merged; // 将前面的部分与排序好的部分连接
  while (prev.next !== null) {
    prev = prev.next; // 把pre指针移动到排序好的部分的末尾
  }
  curr = next;
}

} return dummyHead.next; };

// 获取链表长度 const getLength = (head) => { let count = 0 let node = head; while (node !== null) { count++; node = node.next; } return count; }

// 合并两个有序链表 const merge = (head1, head2) => { const dummyHead = new ListNode(0); let temp = dummyHead, temp1 = head1, temp2 = head2; while (temp1 !== null && temp2 !== null) { if (temp1.val <= temp2.val) { temp.next = temp1; temp1 = temp1.next; } else { temp.next = temp2; temp2 = temp2.next; } temp = temp.next; } if (temp1 !== null) { temp.next = temp1; } else if (temp2 !== null) { temp.next = temp2; } return dummyHead.next; }

```