如何高效且准确地判断两个链表是否相等

import java.util.Objects; // 导入Objects类以使用Objects.equals()

// 假设Node类的定义如下，它支持泛型以处理不同类型的元素
class Node<T> {
    private T elem;
    private Node<T> next;

    public Node(T elem, Node<T> next) {
        this.elem = elem;
        this.next = next;
    }

    public T getElem() {
        return elem;
    }

    public Node<T> getNext() {
        return next;
    }
}

public class LinkedListEqualityChecker {

    /**
     * 检查两个链表是否完全相等。
     * 链表相等意味着它们具有相同的长度，并且在每个对应位置上的元素都相等。
     *
     * @param n 第一个链表的头节点
     * @param m 第二个链表的头节点
     * @param <T> 链表元素的类型
     * @return 如果两个链表相等则返回true，否则返回false
     */
    public static <T> boolean checkEquality(Node<T> n, Node<T> m) {
        // 1. 同时遍历两个链表，直到其中一个或两个都到达末尾
        while (n != null && m != null) {
            // 2. 使用Objects.equals()安全地比较元素。
            //    它能正确处理元素为null的情况，并对对象进行值比较。
            if (!Objects.equals(n.getElem(), m.getElem())) {
                return false; // 发现不相等的元素，立即返回false（早期退出）
            }
            // 3. 如果当前元素相等，则将两个指针同时移动到下一个节点
            n = n.getNext();
            m = m.getNext();
        }

        // 4. 循环结束后，两个链表必须同时到达末尾（即两个指针都为null）才算相等。
        //    这确保了两个链表具有相同的长度。
        return n == null && m == null;
    }

    // 示例用法
    public static void main(String[] args) {
        // 链表1: 1 -> 2 -> 3
        Node<Integer> list1 = new Node<>(1, new Node<>(2, new Node<>(3, null)));
        // 链表2: 1 -> 2 -> 3
        Node<Integer> list2 = new Node<>(1, new Node<>(2, new Node<>(3, null)));
        // 链表3: 1 -> 2 -> 4 (元素不同)
        Node<Integer> list3 = new Node<>(1, new Node<>(2, new Node<>(4, null)));
        // 链表4: 1 -> 2 (长度不同)
        Node<Integer> list4 = new Node<>(1, new Node<>(2, null));
        // 链表5: 空链表
        Node<Integer> list5 = null;
        // 链表6: 空链表
        Node<Integer> list6 = null;
        // 链表7: 1 -> null (包含null元素的链表)
        Node<String> list7 = new Node<>("A", new Node<>(null, new Node<>("C", null)));
        // 链表8: 1 -> null (包含null元素的链表)
        Node<String> list8 = new Node<>("A", new Node<>(null, new Node<>("C", null)));
        // 链表9: 1 -> "B"
        Node<String> list9 = new Node<>("A", new Node<>("B", null));


        System.out.println("list1 == list2? " + checkEquality(list1, list2)); // 预期: true
        System.out.println("list1 == list3? " + checkEquality(list1, list3)); // 预期: false
        System.out.println("list1 == list4? " + checkEquality(list1, list4)); // 预期: false
        System.out.println("list5 == list6? " + checkEquality(list5, list6)); // 预期: true
        System.out.println("list1 == list5? " + checkEquality(list1, list5)); // 预期: false
        System.out.println("list7 == list8? " + checkEquality(list7, list8)); // 预期: true (测试null元素)
        System.out.println("list7 == list9? " + checkEquality(list7, list9)); // 预期: false (测试null元素与非null元素)
    }
}

import java.util.Objects;

// ... (Node类定义与上面相同) ...

public class LinkedListEqualityCheckerRecursive {

    /**
     * 递归方式检查两个链表是否完全相等。
     *
     * @param n 第一个链表的头节点
     * @param m 第二个链表的头节点
     * @param <T> 链表元素的类型
     * @return 如果两个链表相等则返回true，否则返回false
     */
    public static <T> boolean checkEqualityRecursive(Node<T> n, Node<T> m) {
        // 基准情况 1: 两个链表都为空，则相等
        if (n == null && m == null) {
            return true;
        }
        // 基准情况 2: 一个为空，另一个不为空，则不相等（长度不同）
        if (n == null || m == null) {
            return false;
        }
        // 递归步骤:
        // 1. 检查当前节点元素是否相等
        // 2. 如果相等，则递归检查剩余部分是否相等
        return Objects.equals(n.getElem(), m.getElem()) && checkEqualityRecursive(n.getNext(), m.getNext());
    }

    // ... (main方法用于测试，与迭代实现类似) ...
}