java - 链表实现代码中的问题

Question

在我的链表实现中，有两种方法。当我调用一个方法时，它会影响另一种方法的结果。一种方法是 concatenateLL()连接两个列表和一种方法是 getNumberOfNodes()它返回链表中的节点数。对于我的方法连接，我应该返回一个新列表，它是两个列表的连接。但在我的代码中，生成的新列表会影响第一个参数中的列表。假设我通过了列表 l和m和参数，我返回一个新列表。

问题是新的只是列表 l现在包括列表 m 的元素(由于串联)。正因为如此，当我调用getNumberOfNodes()时在名单上l和m ，我得到了错误的值。

这是我的代码:

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
    LinkedList a = l;
    Node l_last = a.getTailNode();
    Node m_first = m.getHeadNode();
    l_last.setNext(m_first);
    a.tail = m.getTailNode();
    return a;
}

public int getNumberOfNodes(Node h) {
    if(h == null)
        return 0;
    return 1 + getNumberOfNodes(h.getNext());
}

public static void print(LinkedList l) {
    Node v = l.getHeadNode();
    while(v != null) {
        System.out.print(v.getElement()+" ");
        v = v.getNext();
    }
    System.out.println();
}

public static void main(String[] args) throws IndexOutOfBoundsException {
    // TODO Auto-generated method stub
    LinkedList l = new LinkedList();
    LinkedList m = new LinkedList();
    l.insertFirst(5);
    l.insertFirst(7);
    l.insertFirst(3);
    l.insertFirst(6);
    print(l);
    m.insertFirst(2);
    m.insertFirst(4);
    m.insertFirst(9);
    m.insertFirst(8);
    m.insertLast(10);
    m.insertLast(12);
    print(m);
    LinkedList n = concatenateLL(l, m);
    print(n);
    System.out.println(l.getNumberOfNodes(l.getHeadNode()));
    System.out.println(m.getNumberOfNodes(m.getHeadNode()));
}

在main方法中，列表长度l应该返回4并列出m应该返回6 。但是在我调用 getNumberOfNodes() 之前调用串联方法之后，我得到的长度为 l如10 (这是列表 n 的节点数，作为 l 和 m 连接的结果)和 m 的长度如15 (我不知道为什么)。

Answer 1

当我看到你的代码时，我猜你习惯用 C/C++ 编写(基于命名约定和预期行为)。您的问题在于进行深层复制。 concatenateLL开头方法，您需要对两个列表进行深层复制，然后您可以按照当前的方式连接它们。

LinkedList a = l; // problem line

在C/C++中，它会调用复制构造函数，但Java没有类似的东西，所以你需要自己实现它。您可以使用方法clone()由 java.lang.Object 声明并覆盖它，但您需要创建深层复制而不是浅层复制，因为您还要更改节点之间的引用，而不仅仅是列表。

例如，该方法可能看起来像这样:

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
   LinkedList a = new LinkedList();

   // copy Nodes, you need to create new instance of them
   for ( int i = 0; i < l.getNumberOfNodes(l.getHeadNode()); ++i )
        a.insertLast( l.getNode( i ) );

   // copy Nodes, you need to create new instance of them
   for ( int i = 0; i < m.getNumberOfNodes(m.getHeadNode()); ++i )
        a.insertLast( m.getNode( i ) );

   return a;
}

但我需要提一下，这个实现有一个 O(n^2)由于方法的复杂性getNode()是 O(n) 。更好的解决方案是使用迭代器，但我不知道你的类是否实现了它。

编辑:将复杂度提高到O(n)我建议你实现标准接口(interface)Iterator无论如何，重点在于保留对当前元素的引用，以便能够简单地获取下一个元素。如果我举一个简单的例子:

Node item = l.getHeadNode();

while( item != null ) {
    // copy the item
    a.insertLast( item );
    item = item.getNext();
}

列表 m 也是如此.