元宝 LeetCode 147. 对链表进行插入排序 Java实现

这道题目要求对链表进行插入排序，核心思想是维护一个已排序的子链表，然后逐个将后续节点插入到正确位置。

解题思路

“lastSorted”：指向已排序部分的最后一个节点（初始为
“head”）。

“curr”：指向当前待插入的节点（初始为
“head.next”）。
3. 插入过程：

• 如果
  “curr” 的值大于等于
  “lastSorted” 的值，说明位置正确，直接后移
  “lastSorted”。
• 否则，从哑节点开始遍历已排序部分，找到第一个值大于
  “curr” 的节点
  “prev.next”，将
  “curr” 插入到
  “prev” 之后。

Java 代码实现

/**

• Definition for singly-linked list.
  */
  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 insertionSortList(ListNode head) {
// 边界条件：空链表或只有一个节点
if (head == null || head.next == null) {
return head;
}

// 创建哑节点，指向链表头
ListNode dummy = new ListNode(0);
dummy.next = head;

// lastSorted 指向已排序部分的最后一个节点
ListNode lastSorted = head;
// curr 指向当前待插入的节点
ListNode curr = head.next;

while (curr != null) {
if (lastSorted.val <= curr.val) {
// 如果当前节点值大于等于已排序部分的最后一个节点，直接后移
lastSorted = lastSorted.next;
} else {
// 否则，从链表头（哑节点之后）开始找插入位置
ListNode prev = dummy;
while (prev.next.val <= curr.val) {
prev = prev.next;
}

// 将 curr 插入到 prev 和 prev.next 之间
lastSorted.next = curr.next; // 从原位置移除 curr
curr.next = prev.next; // curr 指向原 prev.next
prev.next = curr; // prev 指向 curr
}
// 更新 curr 为下一个待处理节点
curr = lastSorted.next;
}

return dummy.next;
}

}

复杂度分析

• 时间复杂度：O(n²)，最坏情况下每次插入都需要遍历整个已排序部分。
• 空间复杂度：O(1)，只使用了常数个额外指针。

示例测试

public class Main {
public static void main(String[] args) {
// 构建链表: 4 -> 2 -> 1 -> 3
ListNode head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);

Solution sol = new Solution();
ListNode result = sol.insertionSortList(head);

// 输出排序后的链表
while (result != null) {
System.out.print(result.val + " ");
result = result.next;
}
// 输出: 1 2 3 4
}

}

如果你需要我帮你把这段代码转写成其他语言（如 Python 或 C++），或者想了解如何进一步优化，随时告诉我！😊