Java 中比较两个链表

2024年9月10日 | 阅读 6 分钟

链表是计算机科学中的基本数据结构，提供动态存储分配和灵活性。它们由通过指针连接的节点组成，每个节点都包含数据和指向下一个节点的引用。在本文中，我们将探讨在 Java 中比较两个链表的各种方法。

我们将介绍三种比较链表的方法：

迭代比较
递归比较
哈希比较

在深入研究代码之前，让我们先在 Java 中创建一个简单的链表实现。

链表实现

// Node class to represent a single node in the linked list
class Node {
    int data;
    Node next;
    // Constructor to initialize a node with given data
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class to represent a singly linked list
class LinkedList {
    Node head; // Points to the first node of the linked list
    // Constructor to initialize an empty linked list
    LinkedList() {
        this.head = null;
    }
    // Method to insert a new node at the end of the linked list
    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode; // If the list is empty, make the new node the head
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // Traverse to the last node
            }
            current.next = newNode; // Add the new node at the end
        }
    }
    // Method to display the elements of the linked list
    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Insert elements into the linked list
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.insert(40);
        // Display the linked list
        System.out.println("Linked List:");
        list.display();
    }
}

输出

Linked List:
10 -> 20 -> 30 -> 40 -> null

1. 迭代比较

迭代方法涉及同时遍历两个链表，并检查每个节点的数据是否相同。如果任何数据不同或列表的长度不相等，则认为列表不相等。否则，它们是相等的。

// Node class to represent a single node in the linked list
class Node {
    int data;
    Node next;
    // Constructor to initialize a node with given data
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class to represent a singly linked list
class LinkedList {
    Node head; // Points to the first node of the linked list
    // Constructor to initialize an empty linked list
    LinkedList() {
        this.head = null;
    }
    // Method to insert a new node at the end of the linked list
    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode; // If the list is empty, make the new node the head
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // Traverse to the last node
            }
            current.next = newNode; // Add the new node at the end
        }
    }
    // Method to display the elements of the linked list
    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
public class Main {
    // Method to compare two linked lists iteratively
    public static boolean iterativeCompare(LinkedList list1, LinkedList list2) {
        Node current1 = list1.head;
        Node current2 = list2.head;
        // Traverse both linked lists simultaneously
        while (current1 != null && current2 != null) {
            if (current1.data != current2.data) {
                return false; // Data in current nodes is different
            }
           current1 = current1.next;
            current2 = current2.next;
        }
        // Check if both lists have been fully traversed
        return current1 == null && current2 == null;
    }
    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        list1.insert(1);
        list1.insert(2);
        list1.insert(3);
        LinkedList list2 = new LinkedList();
        list2.insert(1);
        list2.insert(2);
        list2.insert(3);
        System.out.println("List 1:");
        list1.display();
        System.out.println("List 2:");
        list2.display();
        boolean result = iterativeCompare(list1, list2);
        System.out.println("Lists are equal: " + result);
    }
}

输出

List 1:
1 -> 2 -> 3 -> null
List 2:
1 -> 2 -> 3 -> null
Lists are equal: true

2. 递归比较

递归方法涉及从头节点开始，逐个比较两个链表中节点的数据。如果当前节点具有不同的数据，或者一个列表已到达末尾而另一个列表尚未，则认为列表不相等。否则，递归继续处理下一个节点。

// Node class to represent a single node in the linked list
class Node {
    int data;
    Node next;
    // Constructor to initialize a node with given data
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class to represent a singly linked list
class LinkedList {
    Node head; // Points to the first node of the linked list
    // Constructor to initialize an empty linked list
    LinkedList() {
        this.head = null;
    }
    // Method to insert a new node at the end of the linked list
    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode; // If the list is empty, make the new node the head
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // Traverse to the last node
            }
            current.next = newNode; // Add the new node at the end
        }
    }
    // Method to display the elements of the linked list
    void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
public class Main {
    // Method to compare two linked lists recursively
    public static boolean recursiveCompare(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return true; // Both lists are empty, considered equal
        }
        if (node1 == null || node2 == null) {
            return false; // One list is empty, the other is not
        }
        if (node1.data != node2.data) {
            return false; // Data in current nodes is different
        }
        // Recur for the next nodes
        return recursiveCompare(node1.next, node2.next);
    }
    public static boolean recursiveCompare(LinkedList list1, LinkedList list2) {
        return recursiveCompare(list1.head, list2.head);
    }
    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        list1.insert(1);
        list1.insert(2);
        list1.insert(3);
        LinkedList list2 = new LinkedList();
        list2.insert(1);
        list2.insert(2);
        list2.insert(3);
        System.out.println("List 1:");
        list1.display();
        System.out.println("List 2:");
        list2.display();
        boolean result = recursiveCompare(list1, list2);
        System.out.println("Lists are equal: " + result);
    }
}

输出

List 1:
1 -> 2 -> 3 -> null
List 2:
1 -> 2 -> 3 -> null
Lists are equal: true

3. 哈希比较

哈希方法涉及将链表数据转换为哈希码，然后比较哈希码。可以通过遍历链表并使用哈希函数组合每个节点的数据来获取哈希码。如果两个列表的最终哈希码相同，则认为它们相等。

public static int hashCode(Node node) {
    if (node == null) {
        return 0;
    }
    return node.data + 31 * hashCode(node.next);
}
public static boolean hashingCompare(LinkedList list1, LinkedList list2) {
    int hashCode1 = hashCode(list1.head);
    int hashCode2 = hashCode(list2.head);
    return hashCode1 == hashCode2;
}
public static void main(String[] args) {
    LinkedList list1 = new LinkedList();
    list1.insert(1);
    list1.insert(2);
    list1.insert(3);
    LinkedList list2 = new LinkedList();
    list2.insert(1);
    list2.insert(2);
    list2.insert(3);
    System.out.println("List 1:");
    list1.display();
    System.out.println("List 2:");
    list2.display();
    boolean result = hashingCompare(list1, list2);
    System.out.println("Lists are equal: " + result);
}

输出

List 1:
1 -> 2 -> 3 -> null
List 2:
1 -> 2 -> 3 -> null
Lists are equal: true

在本节中，我们探讨了在 Java 中比较两个链表的三个不同方法。我们了解了迭代、递归和哈希方法，每种方法都有其自身的优点和用例。迭代方法简单高效，但需要更多内存，因为它同时遍历两个列表。递归方法提供了一种优雅的解决方案，并且内存效率高，但由于可能存在堆栈溢出风险，因此可能不适用于极长的列表。

哈希方法是有效的，并且可以处理大型列表，但存在轻微的哈希冲突的可能性。选择合适的比较方法至关重要，具体取决于我们应用程序的具体要求。有了这些知识，我们现在就可以自信地比较链表，并在 Java 程序中利用这些基本数据结构的力量。

下一主题Java 中自动装箱整数对象的比较

Java 中比较两个链表

1. 迭代比较

2. 递归比较

3. 哈希比较

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中比较两个链表

1. 迭代比较

2. 递归比较

3. 哈希比较

相关帖子

Java 中数组的缺点

Java 中的控制台

Java 中使用两个栈实现队列

Java 9 Optional 类改进

Java 中 IntSummaryStatistics getMin() 方法及示例

Java 中的 Kadane 算法

Java 中具有相同数字集的下一个更大的数字

DoubleBuffer allocate() method in Java With Examples

Achilles Number in Java

Java String Max Size

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器