排序链表

发表于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，148. Sort List

先看题目描述

DdPswn.png

大意就是给定一个链表，让我们对其进行排序

算法和思路

归并排序

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

  • 找到链表中点，可以通过快慢指针法找出链表中点，fast 指针每次移动两步，slow 指针每次移动一步，当 fast 指针为空时，slow 指针的前一个节点即为链表中点，然后令链表中点的 next 为空，将链表分为两个子链表
  • 递归的对两个子链表进行归并排序
  • 将有序的两个子链表合并，将合并后链表的头节点返回

这个流程有两个比较关键的地方，第一个是归并排序过程要通过递归来实现，递归的出口的是链表中节点数小于等于 1，即 head == null 或 head.next == null

第二个关键点就是如何将两个有序的子链表合并并返回合并后链表的头节点，合并两个有序子链表的过程可以参照下面的两段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode dump = new ListNode(Integer.MIN_VALUE);
ListNode node1 = sortList(head);
ListNode node2 = sortList(slow);
ListNode pre = dump;
while (node1 != null && node2 != null) {
    if (node1.val <= node2.val) {
        pre.next = node1;
        node1 = node1.next;
    } else {
        pre.next = node2;
        node2 = node2.next;
    }
    pre = pre.next;
}
if (node1 != null) pre.next = node1;
if (node2 != null) pre.next = node2;
return dump.next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode dump = new ListNode(Integer.MIN_VALUE);
ListNode node1 = sortList(head);
ListNode node2 = sortList(slow);
ListNode pre = dump;
dump.next = node1;
while (node1 != null && node2 != null) {
    if (node1.val <= node2.val) {
        node1 = node1.next;
    } else {
        ListNode next = node2.next;
        pre.next = node2;
        node2.next = node1;
        node2 = next;
    }
    pre = pre.next;
}
if (node2 != null) pre.next = node2;
return dump.next;

其中 node1 和 node2 就是两个有序子链表的头节点，两种写法都定义了哑节点 dump 来方便操作，第一种写法比较常规，是每次将较小节点连接到 pre 后来形成合并的链表；第二种写法则是将第二个有序子链表中的节点一个个插入到第一个有序子链表中，从而将两个链表合并起来。第二种写法的合并子链表速度会比第一种略快一点

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = head;
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        prev.next = null;
        ListNode dump = new ListNode(Integer.MIN_VALUE);
        ListNode node1 = sortList(head);
        ListNode node2 = sortList(slow);
        ListNode pre = dump;
        dump.next = node1;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                node1 = node1.next;
            } else {
                ListNode next = node2.next;
                pre.next = node2;
                node2.next = node1;
                node2 = next;
            }
            pre = pre.next;
        }
        if (node2 != null) pre.next = node2;
        return dump.next;
    }
}