如何从 Java 中的单向链表中删除尾巴？

Question

我正在阅读删除单链表最后一个元素的算法。假设我有一个名为 ListNode:

的链表 Object

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

我很困惑这段代码是如何工作的，因为一切都通过 "node"。但是，当return head时，最后一个节点被删除。因此，我想知道它是如何工作的，是否与 Java 中的 "passed by value" 有关？

Answer 1

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

Answer 2

您会注意到该方法正在遍历所有节点直到倒数第二个节点，因为最后一个节点的 next 将是 null。

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

以上代码将为您提供倒数第二个节点，其下一个使用 node.next = null; 设置为 null 这意味着倒数第二个节点现在将成为最后一个节点。

Answer 3

因为 none 的答案很明确（我认为也不正确，因为如果我们有 node.next.next 而我们只有 1 个元素，我们将得到 NullPointerException），我想给我两分钱。

有 3 种情况：

列表为空。直截了当，return null，或者打印列表为空。
列表中有 1 个项目。我们不计算就无法知道这一点（或者我们可以吗？），但请看下面的代码
列表中有多个项目。遍历列表并为前一个变量设置一个临时变量，然后在到达末尾时将 previous.next 设置为 null。

所以，我的方法是将一个初始的前一个变量设置为 null（假设您在列表的开头之前）。然后在 while 循环中，如果它有 1 个项目，它不会执行任何命令（它将跳过它并且 prev 将为空），否则，继续第 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;

希望对您有所帮助。

如何从 Java 中的单向链表中删除尾巴？

How does remove tail from singly Linked List in Java work

java

algorithm

singly-linked-list