在Java中，从单链表中删除尾部是如何工作的

Question

我正在读取删除单链接列表的最后一个元素的算法。假设我有一个名为ListNode的链接列表对象：

public class ListNode {
    private int data;
    private ListNode next;

    public ListNode(int data) {
        this.data = data;
    }

    public int getData() {
        return this.data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return this.next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}

我发现删除列表最后一个节点的方法是：

public ListNode deleteAtTail(ListNode head) {

    if (head == null || head.next == null) return null;
    ListNode node = head;
    while(node.next.next != null) {
        node = node.next;
    }

    node.next = null;
    return head;
}

我很困惑这个代码是如何工作的，因为一切都是通过“节点”。然而，当返回头时，最后一个节点被删除。因此，我想知道它是如何工作的，是否与Java中的“价值传递”有关？

Answer 1

由于没有一个答案是明确的（我认为也不正确，因为如果我们有node.next.next，而我们只有1个元素，我们将得到一个NullPointerException），我想给我2美分。

有3种情况：

1. 列表为空。直接、返回null或打印列表为空
2. 列表中有1项。我们不能不计算就知道这一点（或者我们可以吗？），但请看下面的代码
3. 列表中有多个项。浏览列表，为上一个设置一个临时变量，然后设置上一个。当您到达末尾时，next为null

因此，我的方法是将初始的前一个变量设置为null（假设您在列表的开头之前）。然后在while循环中，如果它有1项，它将不会执行任何命令（它将跳过它，prev将为null），否则，执行第3点。代码如下：

    if(head == null) return;
    ListNode iterator = head;
    ListNode prev = null;
    while(iterator.next !=null) {
        prev = iterator;
        iterator=iterator.next;
    }
    if(prev == null) head = null;
    else prev.next = null;

希望这能有所帮助。

Answer 2

您可以注意到，该方法在所有节点中迭代，直到倒数第二个节点，因为最后一个节点的next将为null。

while(node.next.next != null) {
    node = node.next;
}

上面的代码将为您提供最后一个节点，其下一个节点将使用节点设置为null。next=null 这意味着最后一个节点将成为最后一个节点。

Answer 3

遍历列表的节点，直到node.next.next为空。此时，节点指的是倒数第二个节点，node.next指的是最后一个节点。将node.next设置为null将从列表中删除最后一个节点，因为列表中不再有节点引用它。