Java实现0、1、2值链表排序失效，求技术指导

嘿，作为Java和链表新手碰到这个问题太正常啦！我来帮你捋捋为啥你的代码没生效，再给你靠谱的实现方案~

首先，这类只有0、1、2的链表排序，最常用的是计数法（简单易上手）或者指针拆分拼接法（更锻炼链表操作能力）。你的代码返回原链表，大概率是犯了下面几个常见错误之一：

• 遍历统计的时候直接移动了原链表的head指针，导致后续操作的是空链表或者末尾节点；
• 计数后没有修改原链表的节点值，而是新建了链表但没把新链表的head赋值给原链表的head；
• 用指针拼接的时候，没正确衔接各个节点的next，或者最后没把尾节点的next设为null导致链表有环。

方法一：计数法（新手友好） #

这个方法思路超简单：先统计0、1、2的数量，再遍历链表把节点依次替换成对应数量的0、1、2。

class LinkedList {
    Node head;

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    // 核心排序方法
    void sort012() {
        int count0 = 0, count1 = 0, count2 = 0;
        // 用临时current节点遍历，别碰原head！
        Node current = head;

        // 第一步：统计各数字的数量
        while (current != null) {
            switch (current.data) {
                case 0: count0++; break;
                case 1: count1++; break;
                case 2: count2++; break;
            }
            current = current.next;
        }

        // 第二步：遍历替换节点值
        current = head;
        while (current != null) {
            if (count0 > 0) {
                current.data = 0;
                count0--;
            } else if (count1 > 0) {
                current.data = 1;
                count1--;
            } else {
                current.data = 2;
                count2--;
            }
            current = current.next;
        }
    }

    // 辅助方法：打印链表（方便测试）
    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    // 辅助方法：添加节点到链表末尾
    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(2);
        list.append(0);
        list.append(2);
        list.append(1);
        list.append(1);
        list.append(0);

        System.out.println("排序前的链表:");
        list.printList();

        list.sort012();

        System.out.println("排序后的链表:");
        list.printList();
    }
}

方法二：指针拆分拼接法（进阶练手） #

如果想更深入理解链表指针操作，可以用这个方法：把原链表拆成三个分别存0、1、2的子链表，再把它们拼接起来。

void sort012UsingPointers() {
    // 用虚拟头节点避免处理空链表的边界情况
    Node dummy0 = new Node(-1);
    Node dummy1 = new Node(-1);
    Node dummy2 = new Node(-1);

    Node curr0 = dummy0, curr1 = dummy1, curr2 = dummy2;
    Node current = head;

    // 拆分节点到三个子链表
    while (current != null) {
        if (current.data == 0) {
            curr0.next = current;
            curr0 = curr0.next;
        } else if (current.data == 1) {
            curr1.next = current;
            curr1 = curr1.next;
        } else {
            curr2.next = current;
            curr2 = curr2.next;
        }
        current = current.next;
    }

    // 拼接三个子链表
    curr0.next = dummy1.next != null ? dummy1.next : dummy2.next;
    curr1.next = dummy2.next;
    curr2.next = null; // 必须置空，否则可能出现环

    // 更新原链表的head为排序后的头节点
    head = dummy0.next;
}

你可以对照自己的代码看看是不是踩了我提到的坑——比如是不是不小心移动了原head指针，或者没把排序后的链表头赋值给原链表的head。

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