Medium

题目描述

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

示例 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 * 10^4] 内
  • -10^5 <= Node.val <= 10^5

进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解题思路

本题要求对链表进行排序，有多种解法：

方法一：归并排序（推荐） 采用分治思想，将链表分成两半，递归排序后再合并。关键步骤：

  1. 使用快慢指针找到链表中点，将链表分为两部分
  2. 递归地对两部分进行排序
  3. 合并两个有序链表

这种方法时间复杂度为 O(n log n)，空间复杂度为 O(log n)（递归栈）。

方法二：自底向上归并排序 为了达到 O(1) 空间复杂度，可以使用自底向上的归并排序。从长度为1的子链表开始，逐步合并成长度为2、4、8…的有序链表，直到整个链表有序。

方法三：转换为数组排序 将链表节点值存储到数组中，排序后重建链表。虽然简单，但空间复杂度为 O(n)。

这里实现归并排序方法，它在时间和空间效率上都有很好的表现。

代码实现

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // 找到中点并分割链表
        ListNode* mid = getMid(head);
        ListNode* left = head;
        ListNode* right = mid->next;
        mid->next = nullptr;
        
        // 递归排序
        left = sortList(left);
        right = sortList(right);
        
        // 合并两个有序链表
        return merge(left, right);
    }
    
private:
    ListNode* getMid(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* curr = &dummy;
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }
        
        curr->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # 找到中点并分割链表
        mid = self.getMid(head)
        left = head
        right = mid.next
        mid.next = None
        
        # 递归排序
        left = self.sortList(left)
        right = self.sortList(right)
        
        # 合并两个有序链表
        return self.merge(left, right)
    
    def getMid(self, head):
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def merge(self, l1, l2):
        dummy = ListNode(0)
        curr = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        
        curr.next = l1 if l1 else l2
        return dummy.next

public class Solution {
    public ListNode SortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        // 找到中点并分割链表
        ListNode mid = GetMid(head);
        ListNode left = head;
        ListNode right = mid.next;
        mid.next = null;
        
        // 递归排序
        left = SortList(left);
        right = SortList(right);
        
        // 合并两个有序链表
        return Merge(left, right);
    }
    
    private ListNode GetMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode Merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

var sortList = function(head) {
    if (!head || !head.next) return head;
    
    // 找到中点并分割链表
    const mid = getMid(head);
    const left = head;
    const right = mid.next;
    mid.next = null;
    
    // 递归排序
    const sortedLeft = sortList(left);
    const sortedRight = sortList(right);
    
    // 合并两个有序链表
    return merge(sortedLeft, sortedRight);
};

function getMid(head) {
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

function merge(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = l1 || l2;
    return dummy.next;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型归并排序自底向上归并
时间复杂度O(n log n)O(n log n)
空间复杂度O(log n)O(1)

相关题目