【算法-LeetCode】148. 排序链表（冒泡排序；直接插入排序；简单选择排序）

2023-07-24 19:33:22

148. 排序链表 - 力扣（LeetCode）

文章起笔：2021年10月16日18:01:00

问题描述及示例

给你链表的头结点 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 = []
输出：[]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

这其实就是换了个形式的排序考察。但是受限于链表的遍历方向只能是单向的，所以不大方便使用快速排序这类需要从尾部向前遍历的排序算法（如果要用这类排序的话，那就需要给原本的链表节点增加前置指针或是构造循环链表，这些方法都不是很好）。而像树形选择排序和堆排序也得将链表结构转换为数组形式才更方便，此处也不是很合适。

初步判断下，我先选用了【冒泡排序】、【直接插入排序】、【简单选择排序】这三种较为简单的方法分别实现。后面看到【归并排序】的思路也比较不错。

这些排序的思路就不一一描述了，日后应该会整理各类的排序算法，到时候再作参考。

我的题解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) {
  let dummy = new ListNode(-Infinity, head);
  let p = dummy;
  let q = dummy.next;
  let end = null;
  while(end !== dummy.next) {
    while(q.next !== end) {
      if(p.next.val > q.next.val) {
        // exchangeNode(p.next, q.next);
        p.next = q.next;
        q.next = q.next.next;
        p.next.next = q;
        q = p.next;
      }
      p = p.next;
      q = q.next;
    }
    end = q;
    p = dummy;
    q = dummy.next;
  }
  return dummy.next;
};


提交记录
28 / 28 个通过测试用例
状态：通过
执行用时：8212 ms, 在所有 JavaScript 提交中击败了5.02%的用户
内存消耗：51.1 MB, 在所有 JavaScript 提交中击败了88.99%的用户
时间：2021/10/16 18:05

我的题解2（直接插入排序）

更新：2021年10月17日16:42:50

var sortList = function(head) {
  if(!head) {
    return null;
  }
  let dummy = new ListNode(-Infinity, null);
  let p = head;
  let q = head.next;
  let help = dummy;
  while(p) {
    while(help) {
      if(!help.next || help.next.val > p.val) {
        // insertNode();
        p.next = help.next;
        help.next = p;
        break;
      }
      help = help.next;
    }
    help = dummy;
    p = q;
    q = q ? q.next : q;
  }
  return dummy.next;
};


提交记录
28 / 28 个通过测试用例
状态：通过
执行用时：5832 ms, 在所有 JavaScript 提交中击败了5.04%的用户
内存消耗：52.6 MB, 在所有 JavaScript 提交中击败了72.03%的用户
时间：2021/10/17 16:37

我的题解3（简单选择排序）

更新：2021年10月17日19:39:13

var sortList = function (head) {
  if (!head) {
    return null;
  }
  let dummy = new ListNode(Infinity, head);
  let p = dummy;
  let q = dummy;
  let temp = dummy;
  let rear = dummy;
  let min = null;
  while (p.next) {
    q = p;
    temp = q;
    while (q.next) {
      temp = q.next.val < temp.next.val ? q : temp;
      q = q.next;
    }
    min = temp.next;
    temp.next = temp.next.next;
    min.next = rear.next;
    rear.next = min;
    rear = min;
    p = p.next;
  }
  return dummy.next;
};


提交记录
28 / 28 个通过测试用例
状态：通过
执行用时：6316 ms, 在所有 JavaScript 提交中击败了5.04%的用户
内存消耗：52.9 MB, 在所有 JavaScript 提交中击败了69.38%的用户
时间：2021/10/17 19:35

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

更新：2021年10月17日19:37:17

参考：排序链表 - 排序链表 - 力扣（LeetCode）

【更新结束】

有关参考

《数据结构——用C语言描述（第2版）》耿国华、张德同、周明全等编著高等教育出版社（P317~P349——第9章内部排序）

码农公寓