1

下面的代码构造了 2 个链表，并将它们都传递给构造了第三个合并链表。然而，一旦合并，l1 和 l2（最初构造的）链表就发生了变化。在这段代码中， l1 和 l2 应该在哪里设置为 null ？

编辑：将其设置为 null 的原因是我们不希望客户端将来使用修改后的 l1 或 l2。我们希望有一个明确的合同，一旦合并，我们就会有一个全新的引用，并且以前的引用无效，这样就不会有人认为他们在构建时是链表而使用它们。

public class MergeLinkedList {
    Node first;
    Node last;

    public void add (int val) {
        final Node l = last;
        final Node newNode = new Node(val, null);
        last = newNode;
        if (first == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
    }

    public void displayList() {
        Node tempFirst = first;
        while (tempFirst != null) {
            System.out.print(tempFirst.item + " ");
            tempFirst = tempFirst.next;
        }
    }

    private static class Node {
        int item;
        Node next;

        Node(int element, Node next) {
            this.item = element;
            this.next = next;
        }
    }

    private Node mergeLinkedListRecursive(Node list1, Node list2) {
        if (list1 == null) {
           return list2; 
        }

        if (list2 == null) {
            return list1;
        }

        if (list1.item < list2.item) {
            list1.next = mergeLinkedListRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeLinkedListRecursive(list1, list2.next);
            return list2;
        }
    }

    public void mergeLinkedListRecursion(MergeLinkedList list1, MergeLinkedList list2) {
        first = mergeLinkedListRecursive(list1.first, list2.first);
    }



    public static void main(String[] args) {

        int[] a1 = {1, 3, 5};
        int[] a2 = {2, 4};

        MergeLinkedList l1 = new MergeLinkedList();
        for (int val : a1 ) {
            l1.add(val); 
        }

        MergeLinkedList l2 = new MergeLinkedList();
        for (int val : a2) {
            l2.add(val);
        }

        MergeLinkedList l3 = new MergeLinkedList();
        l3.mergeLinkedListRecursion(l1, l2);
        l3.displayList();
    }
}
4

3 回答 3

2

正确使用由l1和命名的对象的责任在于l2调用者。

也就是说，虽然调用者可能会假设l1并且l2总是评估相同的项目序列，但在l3.mergeLinkedListRecursion(l1, l2);此之后情况并非如此。这是因为该方法执行副作用并改变对象。

在方法调用之后，由调用者来确保正确使用l1andl2。“正确”的用法可能是根本不使用它们。（l1andl2变量仍然评估为两个列表的头部，一个是子列表；只是不是预期的。）

即使可以将参数 (l1和l2) 分配给 null - 即使用引用调用语义 - 也不可能确保所有评估为所述（现在已变异的）对象的变量/字段都分配为 null。

变量/字段是特定对象的名称：如何追踪给定对象的所有名称，比如 Soda - 还是 Pop？可乐？可乐？코카인?

防止此问题的一种方法是使用不可变列表。在这种情况下，合并列表实际上将包含所有新节点，而不是交织现有节点 - 也就是说，对于不可变列表，next只能在构造函数中设置。Haskell 和 Scala 等一些语言遵循这种方法。

另一种方法（我不愿建议）是制作一个“容器容器”；对于链表，它可能只是一个“虚拟头节点”，next当对“使其无效”的列表执行操作时，它将被分配为 null。但是，我发现这是一个难以正确实现的骇人听闻且不需要的解决方案，并且弄脏了原本简单的可变链表实现。

根本问题是突变和副作用，这只是编写非纯代码的丑陋方面之一——一点点文档（和阅读这些文档）可以有很长的路要走。此外，单元测试：测试可以发现错误假设可能引起的问题。

于 2013-06-16T06:55:39.280 回答
0

我不知道你为什么要将 l1 和 l2 设置为 null，但要做到这一点，你需要把它放在这一行之后：

l3.mergeLinkedListRecursion(l1, l2);

为什么您希望将它们设置为空？

于 2013-06-16T06:33:43.920 回答
0

如果一个Node对象在用作 的参数后变得无效mergeLinkedListRecursive()，那么这是节点应该记住的：

class Node {
    ...
    boolean valid = true;
    void markInvalid() { valid = false; }
}

然后mergeLinkedListRecursive()将它们标记为：

list1.markInvalid();
list2.markInvalid();

当然， makeNode的方法首先验证它是否处于有效状态。

于 2013-06-16T06:44:36.807 回答