从单链表中移除重复元素：原理、实现与注意事项_技术教程

本文旨在深入解析从单链表中移除重复元素的算法。我们将详细剖析算法的实现逻辑，着重讲解循环条件的设计，并通过代码示例和注意事项，帮助读者理解该算法的精髓，避免潜在的空指针异常，并确保其在各种场景下的正确运行。

移除单链表重复元素的算法详解

移除单链表中的重复元素是一个常见的算法问题，其核心思想是遍历链表，并针对每个节点，检查其后续节点是否存在相同的数据，如果存在则删除。以下代码展示了如何实现这个算法：

public class SinglyLinkedList {

    Node headNode;

    class Node {
        T data;
        Node nextNode;

        Node(T data) {
            this.data = data;
            this.nextNode = null;
        }
    }

    public static  void removeDuplicates(SinglyLinkedList list) {
        Node current = list.headNode;
        Node compare = null;

        while (current != null && current.nextNode != null) {
            compare = current;
            while (compare.nextNode != null) {
                if (current.data.equals(compare.nextNode.data)) {
                    compare.nextNode = compare.nextNode.nextNode;
                } else {
                    compare = compare.nextNode;
                }
            }
            current = current.nextNode;
        }
    }

    // Example Usage
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList<>();
        list.headNode = list.new Node(1);
        list.headNode.nextNode = list.new Node(2);
        list.headNode.nextNode.nextNode = list.new Node(2);
        list.headNode.nextNode.nextNode.nextNode = list.new Node(3);
        list.headNode.nextNode.nextNode.nextNode.nextNode = list.new Node(4);
        list.headNode.nextNode.nextNode.nextNode.nextNode.nextNode = list.new Node(4);
        list.headNode.nextNode.nextNode.nextNode.nextNode.nextNode.nextNode = list.new Node(5);

        System.out.println("Original List:");
        printList(list);

        removeDuplicates(list);

        System.out.println("List after removing duplicates:");
        printList(list);
    }

    public static  void printList(SinglyLinkedList list) {
        Node current = list.headNode;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.nextNode;
        }
        System.out.println();
    }
}

代码解释：

外层循环： while (current != null && current.nextNode != null)
- current != null：确保 current 指针不为空，防止空指针异常。尤其是在链表为空时， current 直接就是 null。如果移除这个条件，当链表为空时，程序会抛出NullPointerException。
- current.nextNode != null：确保 current 指针的下一个节点不为空。如果下一个节点为空，则说明 current 指向的是链表的最后一个节点，没有必要再进行比较。
内层循环： while (compare.nextNode != null)
- compare.nextNode != null：确保 compare 指针的下一个节点不为空。
重复元素判断： if (current.data.equals(compare.nextNode.data))
- 如果 current 节点的数据与 compare 的下一个节点的数据相等，则说明找到了重复元素，需要删除 compare 的下一个节点。
删除重复元素： compare.nextNode = compare.nextNode.nextNode;
- 将 compare 的 nextNode 指针指向 compare 的下下个节点，从而跳过重复的节点，实现删除操作。
移动 compare 指针： compare = compare.nextNode;
- 如果 current 节点的数据与 compare 的下一个节点的数据不相等，则说明没有找到重复元素，需要将 compare 指针移动到下一个节点。
移动 current 指针： current = current.nextNode;
- 完成一轮内层循环后，将 current 指针移动到下一个节点，继续下一轮的比较。

循环条件的重要性

外层循环的条件 current != null && current.nextNode != null 中的 current != null 至关重要。如果移除这个条件，当链表为空时，current 将为 null，在循环体内部访问 current.data 或 current.nextNode 会导致 NullPointerException。

注意事项和总结