排序链表
题目要求
你需要编写一个算法，对一个单向链表进行排序。输入是链表的头结点 head，你需要对链表中的元素按照升序进行排序，然后返回排序后链表的头结点。
解题思路
要对链表进行排序，有几种不同的算法可以选择：
-
归并排序：这是链表排序中最常用的方法，因为它在链表上的时间复杂度是线性对数的，即 O(nlogn)，而且它不需要额外的空间，这对链表来说是非常合适的。
- 分解：首先，使用快慢指针法找到链表的中点，将链表分成两半。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针就在链表的中点。
- 递归排序：递归地对两个子链表进行排序。
- 合并：将两个已排序的子链表合并成一个有序的链表。
-
插入排序：虽然插入排序在数组排序中效率不高（时间复杂度为 O(n^2)），但在链表排序中，由于插入操作是 O(1) 的，所以在链表不是很长或基本有序的情况下，插入排序也是一个不错的选择。
- 迭代：从头结点开始，对链表进行迭代，将每个节点插入到已排序部分的正确位置。
-
快速排序：链表上的快速排序实现起来比较复杂，且需要额外的空间来存储上一层递归的状态，因此不是最优选择。
在这些方法中，归并排序是最优的选择，因为它提供了最好的平均性能，并且是稳定的排序算法。具体步骤如下：
- 如果链表只有一个节点或为空，则不需要排序，直接返回。
- 使用快慢指针法找到链表的中间节点，将链表从中间分为两部分。
- 对这两部分分别进行归并排序。
- 将两个排序好的链表合并成一个有序链表。
- 返回排序后的链表头结点。
注意，在实际编码时，需要处理好边界条件，如链表为空或只有一个节点的情况，以及在分割和合并过程中对节点的正确处理。
Golang 版本
package main
import (
"fmt"
)
// ListNode is a node in a singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// mergeTwoLists merges two sorted linked lists and returns the head of the sorted list.
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
// sortList sorts the linked list in ascending order using merge sort and returns the head of the list.
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// Find the middle of the list
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
// Split the list into two halves
mid := slow.Next
slow.Next = nil
// Sort each half
left := sortList(head)
right := sortList(mid)
// Merge the sorted halves
return mergeTwoLists(left, right)
}
// Helper function to print the list - for testing purposes.
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
fmt.Println()
}
// main function to execute the code - for testing purposes.
func main() {
// Example usage:
// Create a linked list 4 -> 2 -> 1 -> 3 and sort it.
node3 := &ListNode{Val: 3, Next: nil}
node1 := &ListNode{Val: 1, Next: node3}
node2 := &ListNode{Val: 2, Next: node1}
head := &ListNode{Val: 4, Next: node2}
sortedHead := sortList(head)
printList(sortedHead) // Expected sorted list: 1 2 3 4
}
这段代码实现了链表的归并排序。sortList 函数是排序的主要入口，它使用递归将链表分成两半，然后对每一半进行排序，最后使用 mergeTwoLists 函数将两个有序链表合并成一个有序链表。main 函数提供了一个测试用例，创建了一个链表并调用 sortList 函数进行排序，然后打印排序后的链表。
C++版本
#include <iostream>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
// Function to find the middle of the linked list
ListNode* findMiddle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// Function to merge two sorted linked lists
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
// Main function to sort the linked list
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* mid = findMiddle(head);
ListNode* left = head;
ListNode* right = mid->next;
mid->next = nullptr;
left = sortList(left);
right = sortList(right);
return mergeTwoLists(left, right);
}
};
// Helper function to print the list - for testing purposes.
void printList(ListNode* head) {
while (head) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
// main function to execute the code - for testing purposes.
int main() {
// Example usage:
// Create a linked list 4 -> 2 -> 1 -> 3 and sort it.
ListNode* node3 = new ListNode(3);
ListNode* node1 = new ListNode(1);
node1->next = node3;
ListNode* node2 = new ListNode(2);
node2->next = node1;
ListNode* head = new ListNode(4);
head->next = node2;
Solution solution;
ListNode* sortedHead = solution.sortList(head);
printList(sortedHead); // Expected sorted list: 1 2 3 4
// Clean up memory
while (sortedHead) {
ListNode* temp = sortedHead;
sortedHead = sortedHead->next;
delete temp;
}
return 0;
}
这段 C++代码实现了链表的归并排序。Solution 类中的 sortList 函数是排序的主要入口，它使用递归将链表分成两半，然后对每一半进行排序，最后使用 mergeTwoLists 函数将两个有序链表合并成一个有序链表。main 函数提供了一个测试用例，创建了一个链表并调用 sortList 函数进行排序，然后打印排序后的链表，并在最后清理了分配的内存。
Python 版本
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
# Split the list into two halves
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Split the list into two halves
mid = slow.next
slow.next = None
# Sort each half
left = self.sortList(head)
right = self.sortList(mid)
# Merge the sorted halves
return self.mergeTwoLists(left, right)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
# Helper function to print the list - for testing purposes.
def printList(node):
while node:
print(node.val, end=" ")
node = node.next
print()
# Example usage:
if __name__ == "__main__":
# Create a linked list 4 -> 2 -> 1 -> 3 and sort it.
node3 = ListNode(3)
node1 = ListNode(1, node3)
node2 = ListNode(2, node1)
head = ListNode(4, node2)
solution = Solution()
sorted_head = solution.sortList(head)
printList(sorted_head) # Expected sorted list: 1 2 3 4
这段 Python 代码实现了链表的归并排序。Solution 类中的 sortList 方法是排序的主要入口，它使用递归将链表分成两半，然后对每一半进行排序，最后使用 mergeTwoLists 方法将两个有序链表合并成一个有序链表。printList 函数和 if __name__ == "__main__": 部分提供了一个测试用例，创建了一个链表并调用 sortList 方法进行排序，然后打印排序后的链表。
Java 版本
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Split the list into two halves
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null; // Cut the list into two halves
// Sort each half
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// Merge the sorted halves
return mergeTwoLists(l1, l2);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
// Helper function to print the list - for testing purposes.
class Main {
public static void printList(ListNode node) {
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
// Example usage:
// Create a linked list 4 -> 2 -> 1 -> 3 and sort it.
ListNode node3 = new ListNode(3);
ListNode node1 = new ListNode(1, node3);
ListNode node2 = new ListNode(2, node1);
ListNode head = new ListNode(4, node2);
Solution solution = new Solution();
ListNode sortedHead = solution.sortList(head);
printList(sortedHead); // Expected sorted list: 1 2 3 4
}
}
这段 Java 代码实现了链表的归并排序。Solution 类中的 sortList 方法是排序的主要入口，它使用递归将链表分成两半，然后对每一半进行排序，最后使用 mergeTwoLists 方法将两个有序链表合并成一个有序链表。Main 类中的 printList 方法和 main 方法提供了一个测试用例，创建了一个链表并调用 sortList 方法进行排序，然后打印排序后的链表。
Rust 版本
use std::cell::RefCell; use std::rc::Rc; // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Rc<RefCell<ListNode>>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { next: None, val } } } struct Solution; impl Solution { pub fn sort_list(head: Option<Rc<RefCell<ListNode>>>) -> Option<Rc<RefCell<ListNode>>> { if head.is_none() || head.as_ref().unwrap().borrow().next.is_none() { return head; } // Split the list into two halves let (left, right) = Self::split(head); // Sort each half let left_sorted = Self::sort_list(left); let right_sorted = Self::sort_list(right); // Merge the sorted halves Self::merge_two_lists(left_sorted, right_sorted) } fn split( head: Option<Rc<RefCell<ListNode>>>, ) -> (Option<Rc<RefCell<ListNode>>>, Option<Rc<RefCell<ListNode>>>) { let mut slow = head.clone(); let mut fast = head.unwrap().borrow().next.clone(); let mut prev = None; while let Some(fast_node) = fast { fast = fast_node.borrow().next.clone(); if let Some(fast_node) = fast { prev = slow.clone(); slow = slow.unwrap().borrow().next.clone(); fast = fast_node.borrow().next.clone(); } } let left = head; let right = slow.unwrap().borrow().next.take(); if let Some(prev_node) = prev { prev_node.borrow_mut().next = None; } (left, right) } fn merge_two_lists( l1: Option<Rc<RefCell<ListNode>>>, l2: Option<Rc<RefCell<ListNode>>>, ) -> Option<Rc<RefCell<ListNode>>> { match (l1, l2) { (None, None) => None, (None, Some(node)) => Some(node), (Some(node), None) => Some(node), (Some(node1), Some(node2)) => { if node1.borrow().val < node2.borrow().val { let next = Self::merge_two_lists(node1.borrow_mut().next.take(), Some(node2)); node1.borrow_mut().next = next; Some(node1) } else { let next = Self::merge_two_lists(Some(node1), node2.borrow_mut().next.take()); node2.borrow_mut().next = next; Some(node2) } } } } } fn main() { // Example usage: // Create a linked list 4 -> 2 -> 1 -> 3 and sort it. let node3 = Rc::new(RefCell::new(ListNode::new(3))); let node1 = Rc::new(RefCell::new(ListNode { val: 1, next: Some(node3.clone()) })); let node2 = Rc::new(RefCell::new(ListNode { val: 2, next: Some(node1.clone()) })); let head = Some(Rc::new(RefCell::new(ListNode { val: 4, next: Some(node2.clone()) }))); let sorted_head = Solution::sort_list(head); // Print the sorted list; expected: 1 -> 2 -> 3 -> 4 let mut node = sorted_head; while let Some(n) = node { print!("{} -> ", n.borrow().val); node = n.borrow().next.clone(); } }
这段 Rust 代码实现了链表的归并排序。Solution 结构体中的 sort_list 函数是排序的主要入口，它使用递归将链表分成两半，然后对每一半进行排序，最后使用 merge_two_lists 函数将两个有序链表合并成一个有序链表。main 函数提供了一个测试用例，创建了一个链表并调用 sort_list 函数进行排序，然后打印排序后的链表。
总结
上面给出了使用不同编程语言实现的链表排序算法。这些算法主要使用了归并排序的思想，通过递归将链表分成两半，然后对每一半进行排序，最后合并两个有序链表。每种语言的实现细节略有不同，但整体思路是一致的。这些算法都能有效地对链表进行排序，并且在不同的编程语言中都有相应的数据结构和语法支持。