Medium

题目描述

给定单链表的头节点 head，使用插入排序对链表进行排序，并返回排序后链表的头节点。

插入排序算法的步骤：

  • 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  • 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  • 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表（黑色）最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素（红色），并将其原地插入到排序列表中。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

提示：

  • 列表中的节点数在范围 [1, 5000] 内
  • -5000 <= Node.val <= 5000

解题思路

解题思路

插入排序链表的核心思想是维护一个已排序的部分和一个未排序的部分，不断从未排序部分取出节点插入到已排序部分的正确位置。

算法步骤：

  1. 创建虚拟头节点：为了简化边界处理，创建一个虚拟头节点指向已排序部分
  2. 遍历原链表：从原链表的头节点开始，逐个处理每个节点
  3. 寻找插入位置：对于当前节点，在已排序部分从头开始寻找合适的插入位置
  4. 执行插入操作：将当前节点插入到找到的位置
  5. 更新指针：继续处理下一个节点

关键点：

  • 使用虚拟头节点简化插入到链表头部的情况
  • 每次都从已排序部分的开头开始寻找插入位置
  • 注意保存下一个要处理的节点，因为插入操作会改变链表结构
  • 时间复杂度为 O(n²)，空间复杂度为 O(1)

这种方法虽然时间复杂度较高，但实现简洁，且是原地排序算法。

代码实现

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode* dummy = new ListNode(0);
        ListNode* current = head;
        
        while (current) {
            ListNode* next = current->next;
            
            // 在已排序部分寻找插入位置
            ListNode* prev = dummy;
            while (prev->next && prev->next->val < current->val) {
                prev = prev->next;
            }
            
            // 插入current节点
            current->next = prev->next;
            prev->next = current;
            
            current = next;
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        current = head
        
        while current:
            next_node = current.next
            
            # 在已排序部分寻找插入位置
            prev = dummy
            while prev.next and prev.next.val < current.val:
                prev = prev.next
            
            # 插入current节点
            current.next = prev.next
            prev.next = current
            
            current = next_node
        
        return dummy.next

public class Solution {
    public ListNode InsertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode dummy = new ListNode(0);
        ListNode current = head;
        
        while (current != null) {
            ListNode next = current.next;
            
            // 在已排序部分寻找插入位置
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < current.val) {
                prev = prev.next;
            }
            
            // 插入current节点
            current.next = prev.next;
            prev.next = current;
            
            current = next;
        }
        
        return dummy.next;
    }
}

var insertionSortList = function(head) {
    if (!head || !head.next) return head;
    
    const dummy = new ListNode(0);
    let current = head;
    
    while (current) {
        const next = current.next;
        
        // 在已排序部分寻找插入位置
        let prev = dummy;
        while (prev.next && prev.next.val < current.val) {
            prev = prev.next;
        }
        
        // 插入current节点
        current.next = prev.next;
        prev.next = current;
        
        current = next;
    }
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)外层循环遍历n个节点，内层循环平均需要遍历n/2个节点寻找插入位置
空间复杂度O(1)只使用了常数个额外变量，原地排序算法

相关题目