末端双LL插入卡在回路上

Question

我似乎不明白为什么在双链接列表的末尾插入节点会陷入循环。它要么卡在循环中，要么是空指针。另外，我想知道在处理链表或任何数据结构时，公共节点是更好还是公共无效。

public Node insertEnd(int data) {
    Node newNode = new Node(data);
    newNode.next = null;
    if (head == null) {
        head = newNode;
        return newNode;
    }

    Node last = head;
    while(last!=null) {
        last = last.next;
        last.next = newNode;
    }
    newNode.previous = last;
    return newNode;
}

Answer 1

至于问题的第二部分，它取决于此API的客户端/调用者期望输出的方式。

您编写这个应用编程接口是为了在您正在编写的另一个程序中使用吗？在这种情况下，考虑一下将新创建的节点作为这个应用编程接口的返回值是否有用，或者将其保留为无效是否可以接受。

作为参考，API的Java实现将ull作为返回类型。（https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#addLast（E））

Answer 2

在您的而循环中：

while(last!=null) {
    last = last.next;
    last.next = newNode;
}

第二行设置最后一行。next到新节点所以在下一次迭代中，last将被设置为新节点，谁的下一个字段为空。您只想将设置为最后一个。下一个到新节点一次最后一次。next==null（当您到达列表末尾时）：

while(last.next != null) {
   last = last.next;
}
last.next = newNode;

Answer 3

这是因为这部分逻辑

    Node last = head;
    while(last!=null) {
        last = last.next;
        last.next = newNode; //// This shouldn't happen.
    }

一旦创建了链表，您就可以尝试转到最后一个元素。但是，在遍历过程中，您还更改了节点指向的下一个指针。

尝试将您的逻辑更改为：

public Node insertEnd(int data) {
    Node newNode = new Node(data);
    newNode.next = null;
    if (head == null) {
        head = newNode;
        return newNode;
    }

    Node last = head;
    while(last.next != null) {
        last = last.next;
    }
    last.next = newNode;
    newNode.previous = last;
    return newNode;
}