从链表中移除重复元素

DDD

发布时间：2025-09-26 17:12:19

266人浏览过

来源于php中文网

原创

从链表中移除重复元素

本文详细讲解了如何从单链表中移除重复元素，并深入分析了代码中循环条件的必要性。通过示例代码和解释，帮助读者理解算法的实现原理，避免空指针异常，并掌握链表操作的常见技巧。本文旨在提供一个清晰、易懂的教程，帮助读者更好地理解和应用链表数据结构。

移除链表中的重复元素

在链表数据结构中，移除重复元素是一个常见的操作。本文将深入探讨一种从单链表中移除重复元素的算法，并解释代码中循环条件的意义。

算法实现

以下是用 Java 实现的从单链表中移除重复元素的示例代码：

public class SinglyLinkedList {

    public Node headNode;

    public class Node {
        public T data;
        public Node nextNode;

        public 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;
        }
    }

    // 示例用法
    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);

        removeDuplicates(list);

        // 打印结果，验证是否移除重复元素
        Node current = list.headNode;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.nextNode;
        }
        // 输出: 1 2 3 4
    }
}

代码分析

该算法使用两个指针 current 和 compare 来遍历链表。current 指针用于外层循环，指向当前正在检查的节点。compare 指针用于内层循环，从 current 指针指向的节点开始，遍历链表的剩余部分，查找与 current 节点数据相同的节点。

外层循环条件：while (current != null && current.nextNode != null)

这个条件是算法的关键所在。让我们分解一下：
- current != null: 这个条件确保算法不会在空链表上运行。如果链表为空（headNode 为 null），那么 current 也会是 null，此时循环不会执行，避免空指针异常。
- current.nextNode != null: 这个条件确保 current 指针不会指向链表的最后一个节点。如果 current 指向最后一个节点，那么 current.nextNode 将会是 null，此时内层循环没有必要执行，因为最后一个节点不可能与后面的节点重复。
虽然在非空链表中，即使移除 current != null 条件，算法也能正常工作，但加上这个条件可以确保算法在处理空链表时不会抛出 NullPointerException。 current != null 实际上是一种防御性编程实践，增强了代码的健壮性。
内层循环条件：while (compare.nextNode != null)

这个条件确保 compare 指针不会指向链表的最后一个节点。如果 compare 指向最后一个节点，那么 compare.nextNode 将会是 null，此时没有必要继续比较。

Glif
Glif.app 是一个有趣的AI沙盒工具，用于创建名为 glifs 的微型AI生成器，例如自拍生成器、Meme梗图、表情包、漫画、故事等

下载
重复元素判断：if (current.data.equals(compare.nextNode.data))

如果 current 节点的数据与 compare.nextNode 节点的数据相同，则说明找到了重复元素。此时，将 compare.nextNode 指向 compare.nextNode.nextNode，从而将重复元素从链表中移除。
非重复元素处理：else { compare = compare.nextNode; }

如果 current 节点的数据与 compare.nextNode 节点的数据不同，则说明 compare.nextNode 不是重复元素。此时，将 compare 指针指向下一个节点，继续查找重复元素。
外层循环迭代：current = current.nextNode;

完成内层循环后，将 current 指针指向下一个节点，继续查找重复元素。