#P4050. 排序链表
-
ID: 2292
Tried: 244
Accepted: 98
Difficulty: 5
排序链表
题目内容
给你链表的头结点 head，请将其按 升序 排列并输出 排序后的链表 。
输入描述
输入共一行，包含若干个整数，以空格隔开，表示链表节点的值。
输出描述
输出共一行，包含排序后链表节点的值，用空格隔开。
样例1
输入
4 2 1 3
输出
1 2 3 4
样例2
输入
-1 5 3 4 0
输出
1 2 3 4
提示
- 链表中节点的数目在范围 [0,5∗104] 内
- −105<=Node.val<=105
链表排序
题目分析
本题要求对一个单链表进行升序排序，属于经典链表排序问题。
链表不支持随机访问，因此不能直接使用快速排序等数组常用的排序算法。
解题思路与算法
对于链表排序，常用且高效的方法是『归并排序』：
为什么使用归并排序？
- 归并排序可以很好地适用于链表结构（只需要节点指针的操作，不需要随机访问）。
- 归并排序具有稳定性，且时间复杂度为 O(nlogn)，效率高。
算法步骤
使用归并排序分三步：
- 使用快慢指针找到链表中点，将链表拆分为两个子链表。
- 分别递归对子链表排序。
- 最后合并两个排序好的链表为一个升序链表。
复杂度分析
- 时间复杂度：O(nlogn)（归并排序的标准复杂度）。
- 空间复杂度：O(logn)（递归调用占用的栈空间）。
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;
}