如何在Java实现的循环链表中删除指定值的最后一个出现节点？

我来帮你梳理下这段代码里的问题，然后给出可行的修复方案：

原代码的核心问题 #

• 尾节点（rear）处理错误：原代码只要检测到rear.data == value就直接清空链表，这只适用于链表只有一个节点的场景。如果链表有多个节点且尾节点是目标值，这种处理会直接丢失整个链表的其他节点，完全错误。
• 循环逻辑失效：原循环的条件cur.next != this.head && cur.next.data != value会在遇到第一个匹配节点时就停止遍历，而且循环里的cur没有移动，会直接陷入死循环，根本无法找到最后一个出现的目标节点。
• 边界情况未覆盖：比如链表中不存在目标值时，执行prev.next = tmp.next会抛出空指针异常；也没有处理头节点就是最后一个匹配值的情况。

正确的实现思路 #

要删除循环链表中指定值的最后一个出现节点，我们需要：

1. 完整遍历整个循环链表，跟踪最后一个匹配节点的前驱和匹配节点本身。
2. 针对性处理各种特殊场景：空链表、无匹配节点、所有节点都是目标值、匹配节点是头/尾节点等。

修正后的代码 #

public void deleteLastOccurrence(int value) {
    // 空链表直接返回
    if (this.head == null) {
        return;
    }

    Element cur = this.head;
    Element lastMatchPrev = null; // 记录最后一个匹配节点的前驱
    Element lastMatchNode = null; // 记录最后一个匹配节点

    // 用do-while遍历整个循环链表，确保每个节点都被检查到
    do {
        if (cur.next.data == value) {
            // 每次找到匹配节点时，更新最后一次的记录
            lastMatchPrev = cur;
            lastMatchNode = cur.next;
        }
        cur = cur.next;
    } while (cur != this.head); // 回到头节点时停止遍历

    // 没有找到任何匹配节点，直接返回
    if (lastMatchNode == null) {
        return;
    }

    // 处理所有节点都是目标值的情况（比如单节点链表或全value链表）
    if (lastMatchNode == this.head && lastMatchPrev == this.rear) {
        this.head = this.rear = null;
        return;
    }

    // 如果最后一个匹配节点是尾节点，更新rear为它的前驱
    if (lastMatchNode == this.rear) {
        this.rear = lastMatchPrev;
    }

    // 如果最后一个匹配节点是头节点，更新head为下一个节点
    if (lastMatchNode == this.head) {
        this.head = this.head.next;
    }

    // 执行删除操作：让前驱节点指向匹配节点的下一个节点
    lastMatchPrev.next = lastMatchNode.next;
}

代码关键点解释 #

• 使用do-while循环：因为循环链表的头节点的前驱是尾节点，do-while会先执行一次检查，避免漏掉头节点之后的第一个节点的判断，确保遍历完整。
• 跟踪最后匹配节点：遍历过程中不断更新最后一次匹配的节点和它的前驱，这样遍历结束后就能直接操作这两个节点完成删除。
• 特殊场景处理：单独处理了全匹配节点、头/尾节点匹配的情况，保证链表的循环结构不会被破坏。
• 空指针防护：增加了无匹配节点的判断，避免后续操作抛出异常。

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