自定义Java单链表去重：双指针法测试用例与O(n²)方案可行性

以下针对你提出的三个核心问题逐一解答：

一、需要测试的边缘用例 #

为确保removeDuplicates方法覆盖所有场景，务必测试以下边缘情况：

• 空链表：调用去重方法后无异常，链表仍为空
• 单节点链表：去重后链表保持原样，仅保留唯一节点
• 所有节点值完全重复：例如2->2->2->2，去重后仅剩一个2
• 连续重复节点：例如1->1->2->2->3，去重后应为1->2->3
• 末尾节点重复：例如1->2->3->2，去重后应为1->2->3；或5->3->5，去重后为5->3
• 重复值分散出现：例如1->3->2->3->1->4，去重后为1->3->2->4
• 仅两个重复节点：例如7->7，去重后仅剩一个7

二、O(n²)复杂度方案的可接受性 #

在禁止使用Java Collections的前提下，O(n²)方案的可接受性取决于链表规模：

• 若链表节点数较少（如几百到几千级别），O(n²)的时间开销完全在可接受范围内，实际运行不会有明显延迟
• 若链表节点数较大（如上万甚至十万级别），O(n²)的时间复杂度会导致运行时间急剧增加，此时该方案就不太适用。但受限于不能用Collections，若必须保持原链表顺序，这已是原地去重的最优选择之一

三、当前双指针法的合理性与更优方案 #

当前方案的合理性 #

你采用的双指针法是非常合适的原地去重实现：

• 逻辑直观易懂：一个指针固定当前节点，另一个指针扫描后续节点删除重复值
• 空间复杂度为O(1)：仅使用几个指针变量，不需要额外存储空间
• 能保持原链表的元素顺序：这是很多场景下的硬性要求

更优方案（视场景而定） #

如果允许修改链表的元素顺序，可以采用以下优化方案，将时间复杂度降至O(n log n)：

1. 对单链表进行排序（例如使用归并排序，链表的归并排序空间复杂度可做到O(log n)）
2. 排序后使用单指针遍历去重：遍历过程中跳过连续重复的节点，时间复杂度O(n)
   整体时间复杂度为O(n log n)，比O(n²)更高效，但缺点是改变了原链表的元素顺序

如果必须保持原顺序且追求O(n)时间复杂度，在禁止Java Collections的情况下，你可以自行实现简单的哈希结构（比如用数组模拟哈希表，前提是节点值的范围已知且较小），遍历链表时记录已出现的元素，遇到重复直接删除，时间复杂度O(n)，空间复杂度O(n)，但需要额外的存储空间。

你的参考代码 #

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

class SinglyLinkedList {
    Node head;

    public void add(int value) {
        Node newNode = new Node(value);

        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }

    public void removeDuplicates() {
        Node current = head;

        while (current != null) {
            Node runner = current;

            while (runner.next != null) {
                if (runner.next.value == current.value) {
                    runner.next = runner.next.next;
                } else {
                    runner = runner.next;
                }
            }

            current = current.next;
        }
    }

    public void printList() {
        Node current = head;

        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.add(3);
        list.add(5);
        list.add(3);
        list.add(7);
        list.add(5);

        list.removeDuplicates();
        list.printList();
    }
}

样例输入输出：

观测输出：3 5 7
预期输出与观测输出一致

内容的提问来源于stack exchange，提问作者Elder Pérez