0

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

问题是新的只是列表l，现在包含列表的元素m（由于连接）。正因为如此，当我调用getNumberOfNodes()list land时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 方法中， list 的长度l应该返回4并且 listm应该返回6。但是在调用之前调用连接方法之后getNumberOfNodes()，我得到las的长度（这是由于 and的连接而导致的 list 的节点数）和 as 的长度10（我不知道为什么）。nlmm15

4

3 回答 3

1

当我看到你的代码时，我猜你习惯于用 C/C++ 编写（基于命名约定和预期行为）。您的问题在于制作 deep copy。在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)我建议您实现标准接口Iterator无论如何，关键在于保持对当前元素的引用能够简单地获得下一个。如果我举一个简单的例子：

Node item = l.getHeadNode();

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

列表也是如此m。

于 2012-09-12T05:36:41.197 回答
0 
public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
    LinkedList a = new LinkedList();
    Node l_last = l.getHeadNode();
    Node m_first = m.getHeadNode();
    while(l_last != null) {
        a.insertLast(l_last.getElement());
        l_last = l_last.getNext();
    }
    while(m_first != null) {
        a.insertLast(m_first.getElement());
        m_first = m_first.getNext();
    }       
     return a;
}
于 2012-09-12T06:01:34.417 回答
0

是的，LInkedList a = l;不会创建linked-list 的副本l。

如果您不想修改l.

于 2012-09-12T05:38:42.237 回答