[路飞]_leetcode-148-排序链表

[题目地址][B站地址]

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

示例 1：

输入： head = [4,2,1,3]
输出： [1,2,3,4]
复制代码

示例 2：

输入： head = [-1,5,3,4,0]
输出： [-1,0,3,4,5]
复制代码

示例 3：

输入： head = []
输出： []
复制代码

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• -105 <= Node.val <= 105

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

解题思路

归并排序

首先讲一下本题的最优解，同时也是官方题解。

将原链表拆分为每一个节点为链表的子链表。

然后将它们两两合并，合并过程中会对比两个节点的大小，小的在前，大的在后。

再将合并后的子链表两两进行合并，同样，合并过程中，比较两个链表节点的大小，小的在前，大的在后。

直到所有子链表合并为一个链表，就完成了输入链表的排序。

因为每一个链表节点是一个对象，所以在整个拆分过程中是不会增加额外的存储空间的。

同时也是因为链表这种数据结构不像数组，所以在拆分及合并过程中，会比较繁琐，这里我偷个懒就不去实现对应代码了，感兴趣的小伙伴可以去看一下官方题解。

暴力美学

接下来讲一下本题的另外一种我比较喜欢的解题思路。

首先遍历链表，将所有节点值存储到一个数组中。

然后对数组进行 sort 升序排序。

根据排序后的结果构建结果链表即可。

这样的一种解题方式，时间复杂度同样是 O(n log n) 的，但是因为我们开辟了一个数组存储节点值以及创建了新的结果链表，所以空间复杂度是 O(n) 的。

代码实现

var sortList = function(head) {
  // 特判输入链表为空，返回空
  if(head === null) return null;
  // 初始化数组存储链表中的节点值
  const arr = [];
  while(head){
    arr.push(head.val);
    head = head.next;
  }
  // 对节点值数组升序排序
  arr.sort((a,b) => a-b)
  // 根据排序数组构造结果链表
  head = new ListNode(arr[0])
  let cur = head;
  for(let i = 1;i<arr.length;i++){
    cur.next = new ListNode(arr[i])
    cur = cur.next;
  }
  // 返回结果链表
  return head;
};
复制代码

至此我们就完成了 leetcode-148-排序链表

如有任何问题或建议，欢迎留言讨论！