java - 末端双重 LL 插入卡在环上

Question

我似乎无法弄清楚为什么在双向链表的末尾插入节点会陷入循环。要么陷入循环，要么陷入空指针。另外我想知道在处理链表或任何数据结构时 public Node 更好还是 public void 更好。

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

嗯，就是因为这部分逻辑

    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;
}