Java实现int型链表addToBack方法执行后列表为空问题求解

问题原因 #

你的代码核心错误出在addToBack方法的两处逻辑：

1. 新节点构造参数错误：tail.nextNode = new Node(x, tail);这行代码中，Node构造方法的第二个参数是新节点的后继指针nextNode，你传入了当前的尾节点tail，导致新节点的后继指向了前一个节点，直接形成循环链表。toString方法遍历链表时会陷入无限循环，不会走到终止条件ptr == null，最终可能触发内存溢出等异常，表现为链表看似为空。
2. 指针维护缺失：空链表添加元素的分支没有更新成员变量tail，同时你直接使用成员变量tail作为遍历指针，会覆盖原有tail的取值，后续如果要利用tail优化添加效率会出问题。另外部分构造方法和addToFront方法也没有维护tail指针，存在隐藏bug。

修复方案 #

1. 修复addToBack方法

你可以选择两种实现方式：

方式一：每次遍历找尾节点（无需依赖tail成员变量，兼容性好）

public void addToBack(int x) {
    if (head == null) {
        head = new Node(x, null);
        return;
    }
    // 用局部变量遍历，不修改成员变量tail
    Node curr = head;
    while (curr.nextNode != null) {
        curr = curr.nextNode;
    }
    // 新节点的后继是null，而非前一个节点
    curr.nextNode = new Node(x, null);
}

方式二：利用tail成员变量实现O(1)效率添加（推荐，性能更高）

需要同时修复其他方法的tail维护逻辑：
首先修复addToBack：

public void addToBack(int x) {
    Node newNode = new Node(x, null);
    if (head == null) {
        head = newNode;
        tail = newNode;
        return;
    }
    tail.nextNode = newNode;
    tail = newNode;
}

然后修复addToFront，补充空链表场景的tail赋值：

public void addToFront(int x) {
    head = new Node(x, head);
    // 空链表添加第一个元素时同步更新tail
    if (tail == null) {
        tail = head;
    }
}

再修复拷贝构造方法，避免局部变量覆盖成员变量：

public LinkedListOfInts(LinkedListOfInts other) {
    Node currTail = null;
    for (Node n = other.head; n != null; n = n.nextNode) {
        if (currTail == null)
            this.head = currTail = new Node(n.value, null);
        else {
            currTail.nextNode = new Node(n.value, null);
            currTail = currTail.nextNode;
        }
    }
    // 给成员变量tail赋值
    this.tail = currTail;
}

最后修复数组构造方法，补充tail赋值：

public LinkedListOfInts(int[] other) {
    if (other.length == 0) {
        head = null;
        tail = null;
        return;
    }
    Node[] nodes = new Node[other.length];
    for (int index = 0; index < other.length; index++) {
        nodes[index] = new Node(other[index], null);
        if (index > 0) {
            nodes[index - 1].nextNode = nodes[index];
        }
    }
    head = nodes[0];
    tail = nodes[nodes.length - 1];
}

内容的提问来源于stack exchange，提问作者user16854661