链表排序

题目分析

本题要求对一个单链表进行升序排序，属于经典链表排序问题。

链表不支持随机访问，因此不能直接使用快速排序等数组常用的排序算法。

解题思路与算法

对于链表排序，常用且高效的方法是『归并排序』：

为什么使用归并排序？

• 归并排序可以很好地适用于链表结构（只需要节点指针的操作，不需要随机访问）。
• 归并排序具有稳定性，且时间复杂度为 $O(n\log n)$，效率高。

算法步骤

使用归并排序分三步：

1. 使用快慢指针找到链表中点，将链表拆分为两个子链表。
2. 分别递归对子链表排序。
3. 最后合并两个排序好的链表为一个升序链表。

复杂度分析

• 时间复杂度：$O(n\log n)$（归并排序的标准复杂度）。
• 空间复杂度：$O(\log n)$（递归调用占用的栈空间）。

Python 代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 归并排序主函数
def sortList(head):
    if not head or not head.next:
        return head

    # 快慢指针找中点
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    # 递归排序左右两半
    left = sortList(head)
    right = sortList(mid)

    # 合并排序后的链表
    dummy = ListNode()
    cur = dummy
    while left and right:
        if left.val <= right.val:
            cur.next, left = left, left.next
        else:
            cur.next, right = right, right.next
        cur = cur.next
    cur.next = left if left else right
    return dummy.next

# 输入
vals = list(map(int, input().split()))
dummy = ListNode()
cur = dummy
for v in vals:
    cur.next = ListNode(v)
    cur = cur.next

# 排序链表
res = sortList(dummy.next)

# 输出
ans = []
while res:
    ans.append(str(res.val))
    res = res.next
print(' '.join(ans))

Java 代码

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    // 归并排序主函数
    public static ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        ListNode dummy = new ListNode(0), cur = dummy;
        while(left != null && right != null){
            if(left.val <= right.val){
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left != null ? left : right;
        return dummy.next;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] vals = sc.nextLine().trim().split(" ");
        ListNode dummy = new ListNode(0), cur = dummy;
        for(String val: vals){
            if(!val.isEmpty()){
                cur.next = new ListNode(Integer.parseInt(val));
                cur = cur.next;
            }
        }

        ListNode res = sortList(dummy.next);
        StringBuilder sb = new StringBuilder();
        while(res != null){
            sb.append(res.val).append(" ");
            res = res.next;
        }
        System.out.println(sb.toString().trim());
    }
}

C++ 代码

#include <iostream>
#include <sstream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 归并排序主函数
ListNode* sortList(ListNode* head) {
    if(!head || !head->next) return head;

    ListNode* slow = head;
    ListNode* fast = head->next;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* mid = slow->next;
    slow->next = nullptr;

    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);

    ListNode dummy(0);
    ListNode* cur = &dummy;
    while(left && right){
        if(left->val <= right->val){
            cur->next = left;
            left = left->next;
        } else {
            cur->next = right;
            right = right->next;
        }
        cur = cur->next;
    }
    cur->next = left ? left : right;
    return dummy.next;
}

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    int num;
    ListNode dummy(0), *cur = &dummy;
    while(ss >> num){
        cur->next = new ListNode(num);
        cur = cur->next;
    }

    ListNode* res = sortList(dummy.next);
    while(res){
        cout << res->val;
        if(res->next) cout << " ";
        res = res->next;
    }
    cout << endl;
    return 0;
}

Leetcode 33.排序链表-原题链接

题目内容

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

输入描述

输入共一行，包含若干个整数，以空格隔开，表示链表节点的值。

输出描述

输出共一行，包含排序后链表节点的值，用空格隔开。

样例1

输入

4 2 1 3

输出

1 2 3 4

样例2

输入

-1 5 3 4 0

输出

1 2 3 4

提示

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