本文详解链表冒泡排序中节点交换的正确实现，重点解决因未更新头节点引用导致排序失败（如输入 [2,1,4,3] 输出仅 [2]）的核心问题，并提供可运行、边界健壮的完整代码。
本文详解链表冒泡排序中节点交换的正确实现，重点解决因未更新头节点引用导致排序失败（如输入 `[2,1,4,3]` 输出仅 `[2]`）的核心问题，并提供可运行、边界健壮的完整代码。
在 Java 中对单向链表执行冒泡排序时，若采用交换节点（而非仅交换数据域）的方式，必须严格维护链表结构的完整性——尤其是 head 引用的更新。原代码的根本缺陷在于：swap() 方法为 void 类型，虽在方法内部修改了节点指针关系，但无法将新头节点（当首节点参与交换时）反馈给调用方，导致外部 head 变量仍指向旧首节点，后续遍历断裂，最终仅输出孤立头节点（如 [2,1,4,3] → [2]）。
✅ 正确实现要点
- swap() 必须返回新的头节点：当 current == head 时，next 成为新头节点，需返回 next；否则头节点不变，返回原 head。
- 调用处必须重新赋值 head：head = swap(head, current, next, prev);
- 指针更新需严谨：确保 prev.next、current.next、next.next 三者指向逻辑自洽，避免空指针或环。
以下是修正后的完整可运行代码（含 Node 定义与测试）：
class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
public class BubbleLinkedSort {
// 返回新的 head 节点
public static Node swap(Node head, Node current, Node next, Node prev) {
if (current == head) {
// 当前节点是头节点：next 成为新头
current.next = next.next;
next.next = current;
return next; // 关键：返回新头
} else {
// 普通情况：调整 prev、current、next 的 next 指针
prev.next = next;
current.next = next.next;
next.next = current;
return head; // 头未变
}
}
public static Node bubbleSort(Node head) {
if (head == null || head.next == null) {
return head; // 空链表或单节点，直接返回
}
boolean sorted = false;
while (!sorted) {
sorted = true;
Node prev = null;
Node current = head;
Node next = head.next;
while (next != null) {
if (current.data <= next.data) {
// 顺序正确，推进指针
prev = current;
current = next;
next = next.next;
} else {
// 逆序，执行交换并更新 head（关键！）
head = swap(head, current, next, prev);
// 交换后：prev 指向原 next（现 current 前驱），current 和 next 角色互换
// 为保持遍历连续性，需重新定位 prev/current/next：
if (prev == null) {
// 说明刚交换了头节点，新 head 即 current 的新前驱（即 next）
prev = head; // 实际上 prev 应为 head 的前驱，但头无前驱，故设为 head
current = head;
next = head.next;
} else {
// prev 不为空：交换后 prev.next 已指向 next（即新 current）
current = prev.next; // 新 current 是 prev.next（即原 next）
next = current.next; // 新 next 是 current.next
}
sorted = false;
}
}
}
return head;
}
// 辅助方法：打印链表
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
// 测试示例
public static void main(String[] args) {
// 测试用例 1: [2,1,4,3]
Node head1 = new Node(2);
head1.next = new Node(1);
head1.next.next = new Node(4);
head1.next.next.next = new Node(3);
System.out.print("Original: "); printList(head1);
head1 = bubbleSort(head1);
System.out.print("Sorted: "); printList(head1); // 输出: 1 -> 2 -> 3 -> 4
// 测试用例 2: [1,4,3,2,1]
Node head2 = new Node(1);
head2.next = new Node(4);
head2.next.next = new Node(3);
head2.next.next.next = new Node(2);
head2.next.next.next.next = new Node(1);
System.out.print("Original: "); printList(head2);
head2 = bubbleSort(head2);
System.out.print("Sorted: "); printList(head2); // 输出: 1 -> 1 -> 2 -> 3 -> 4
}
}⚠️ 注意事项与最佳实践
- 不要忽略指针重定位：交换后 current 和 next 的逻辑位置已改变，必须根据 prev 的新状态重新设置三指针，否则内层 while 循环会跳过元素或陷入死循环。
- 边界条件全覆盖：bubbleSort() 开头直接处理 null 和单节点情况，避免空指针异常。
- 避免副作用陷阱：Java 中对象引用按值传递，head 变量本身不可被方法内部修改，因此必须显式返回并重新赋值。
- 时间复杂度：仍是 O(n²)，但空间复杂度为 O(1)，符合链表原地排序要求。
通过以上修正，链表冒泡排序能稳定处理任意输入顺序，真正实现基于节点交换的结构化排序，而非依赖数据域交换的“伪排序”。
