LeetCode 147. 对链表进行插入排序

Categories:

题目描述
思路分析
1. 解法一：链表插入排序（推荐）
相似题目

题目描述

✅ 147. 对链表进行插入排序

思路分析

解法一：链表插入排序（推荐）

核心思路：

用哑节点维护已排序链表头。

依次取出原链表节点，在线性扫描中找到插入位置。

将节点插入到合适位置，继续处理下一个节点。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示链表长度。

空间复杂度：O(1)，原地插入。

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;

            ListNode pre = dummy;
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }

            // 将 cur 插入到 pre 之后
            cur.next = pre.next;
            pre.next = cur;

            cur = next;
        }

        return dummy.next;
    }
}

func insertionSortList(head *ListNode) *ListNode {
	dummy := &ListNode{Val: 0}
	cur := head

	for cur != nil {
		next := cur.Next

		pre := dummy
		for pre.Next != nil && pre.Next.Val < cur.Val {
			pre = pre.Next
		}

		// 将 cur 插入到 pre 之后
		cur.Next = pre.Next
		pre.Next = cur

		cur = next
	}

	return dummy.Next
}

相似题目

题目	难度	考察点
148. 排序链表	中等	归并排序
147. 对链表进行插入排序	中等	链表排序
143. 重排链表	中等	链表操作
21. 合并两个有序链表	简单	链表合并
206. 反转链表	简单	链表反转
86. 分隔链表	中等	链表划分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/87842493