Java链表节点交换实现冒泡排序出错问题排查

问题描述 #

我编写了一段通过交换节点实现链表冒泡排序的Java代码：

public class BubbleLinkedSort {
    public static void swap(Node head, Node current, Node next, Node prev){
        if(current == head){
            current.next = next.next;
            next.next = current;
        }
        else{
            prev.next = current.next;
            current.next = next.next;
            next.next = current;
        }
    }

    public static void bubbleSort(Node head){
        if(head == null){
            System.out.println("List is empty");
            return;
        }
        else if(head.next == null){
            System.out.println("only one element in LL");
            return;
        }
        else{
            boolean sorted = false;

            while(!sorted){
                sorted = true;
                Node prev = null;
                Node next = head.next;
                Node current = head;

                while(next != null){
                    if(current.data <= next.data){
                        prev = current;
                        current = current.next;
                        next = next.next;
                    }
                    else{
                        swap(head,current,next,prev);
                        if(current == head)
                        {
                            head = next;
                        }
                        prev = next;
                        next = current.next;
                        sorted = false;
                    }
                }
            }
        }
    }
}

运行异常：

• 当链表首元素小于次元素时排序正常，比如输入<1,4,3,2,1>，输出<1,1,2,3,4>；
• 当首元素大于次元素时结果错误，比如输入<2,1,4,3>，输出仅为<2>。

错误根源 #

1. Java值传递导致头节点引用失效：swap方法中传入的head是原引用的副本，方法内对head的修改不会影响bubbleSort方法里的head变量。即使交换后写了head = next，此时链表结构已经因swap内的操作发生断裂，后续指针遍历逻辑出错。
2. 指针更新不严谨：交换头节点后，bubbleSort内的current、next指针没有正确关联新的链表结构，导致遍历提前终止，链表出现断裂。
3. 方法未返回更新后的头节点：外部调用者持有的始终是旧的头节点引用，当头节点被交换后，旧头节点的next可能指向错误位置，导致只能看到部分节点。

修复后的代码 #

public class BubbleLinkedSort {
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 移除head参数，通过prev是否为null判断是否是头节点交换
    public static void swap(Node current, Node nextNode, Node prev){
        if(prev == null){
            current.next = nextNode.next;
            nextNode.next = current;
        } else {
            prev.next = nextNode;
            current.next = nextNode.next;
            nextNode.next = current;
        }
    }

    // 返回更新后的头节点，让外部拿到正确的链表起始
    public static Node bubbleSort(Node head){
        if(head == null){
            System.out.println("List is empty");
            return head;
        }
        if(head.next == null){
            System.out.println("only one element in LL");
            return head;
        }
        
        boolean sorted = false;
        Node newHead = head;

        while(!sorted){
            sorted = true;
            Node prev = null;
            Node current = newHead;
            Node nextNode = current.next;

            while(nextNode != null){
                if(current.data <= nextNode.data){
                    prev = current;
                    current = current.next;
                    nextNode = nextNode.next;
                } else {
                    swap(current, nextNode, prev);
                    // 交换头节点时更新newHead
                    if(prev == null){
                        newHead = nextNode;
                    }
                    // 交换后修正指针位置
                    prev = nextNode;
                    nextNode = current.next;
                    sorted = false;
                }
            }
        }
        return newHead;
    }

    // 测试用例
    public static void printList(Node head){
        Node temp = head;
        while(temp != null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        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.println("排序前：");
        printList(head1);
        Node sortedHead = bubbleSort(head1);
        System.out.println("排序后：");
        printList(sortedHead);
    }
}

关键修复说明 #

• 返回新头节点：外部调用者通过返回值获取排序后的链表起始，避免旧头节点引用失效的问题；
• 简化swap方法：去掉head参数，用prev == null判断是否交换头节点，避免值传递带来的引用问题；
• 修正指针逻辑：交换节点后，prev、nextNode的更新逻辑更严谨，确保链表遍历不会断裂；
• 增加Node内部类：补充完整的链表节点定义，让代码可直接运行测试。

内容的提问来源于stack exchange，提问作者ashwini chaudhary