148. Sort List

148. Sort Listopen in new window

🟠 🔖 链表 双指针 分治 排序 归并排序 🔗 LeetCodeopen in new window

题目

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

题目大意

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

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

解题思路

使用归并排序（Merge Sort）对链表进行排序，归并排序的核心思想是分治和合并。

首先，对链表进行分治，将链表一分为二。可以通过快慢指针找到链表的中点，然后分别对左右两部分进行排序。
对左右两个已排序的链表进行合并。合并两个有序链表的过程可以参考合并两个有序数组的算法。
递归地对左右两部分链表进行排序和合并，直到每个部分的长度为 1。
最终得到一个完全有序的链表。

通过归并排序，可以在链表排序中达到 O(n log n) 的时间复杂度，其中 n 是链表的长度，且不需要额外的空间。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  if (!head || !head.next) return head;

  // 找到链表中点
  const mid = findMid(head);
  const left = head;
  const right = mid.next;
  mid.next = null; // 断开链表

  // 递归对左右两部分进行排序
  const sortLeft = sortList(left);
  const sortRight = sortList(right);

  // 合并两个有序链表
  return merge(sortLeft, sortRight);
};

// 找到链表的中点（快慢指针）
var findMid = function (head) {
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

// 合并两个有序链表
var merge = function (a, b) {
  let res = new ListNode(0);
  let cur = res;
  while (a && b) {
    if (a.val < b.val) {
      cur.next = a;
      a = a.next;
    } else {
      cur.next = b;
      b = b.next;
    }
    cur = cur.next;
  }
  // 处理剩余的节点
  if (a) {
    cur.next = a;
  }
  if (b) {
    cur.next = b;
  }
  return res.next;
};

148. Sort List

# 148. Sort Listopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

148. Sort Listopen in new window

题目

题目大意

解题思路

代码

相关题目