单链表连续重复节点移除问题求助：remainingNodes方法不符合预期

你的代码目前仅能保留连续重复节点的第一个，移除后续重复节点，但根据你给出的示例需求，我们需要调整逻辑来匹配两种可能的规则（根据你的示例存在两种解读，下面分别给出解决方案）：

规则1：移除整个连续重复节点段（示例1匹配） #

规则说明：找到最左侧的连续重复节点段（长度≥2），将该段完全移除；重复此操作直到没有连续重复段为止。

原代码问题分析 #

• 原代码仅跳过重复节点，保留了第一个重复节点，没有移除整个重复段。
• 仅遍历一次链表，未处理移除重复段后新出现的连续重复（比如示例1中移除2的段后，3的段变成新的重复段）。

修改后的代码 #

public int remainingNodes() {
    if (start == null) {
        return 0;
    }

    // 哑节点处理头节点被移除的情况
    Node dummy = new Node(-1);
    dummy.next = start;
    boolean hasRemoved;

    do {
        hasRemoved = false;
        Node prev = dummy;
        Node curr = dummy.next;

        while (curr != null && curr.next != null) {
            // 找到连续重复段
            if (curr.value == curr.next.value) {
                hasRemoved = true;
                int duplicateVal = curr.value;
                // 移动到重复段末尾
                while (curr != null && curr.value == duplicateVal) {
                    curr = curr.next;
                }
                // 移除整个重复段
                prev.next = curr;
                break; // 处理完一个段后重新从头检查
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
    } while (hasRemoved);

    // 统计剩余节点数
    int count = 0;
    Node curr = dummy.next;
    while (curr != null) {
        count++;
        curr = curr.next;
    }
    start = dummy.next;
    return count;
}

逻辑解释 #

• 哑节点dummy：避免头节点被移除时的特殊处理，所有移除操作通过prev.next完成。
• do-while循环：每次处理完一个重复段后，重新从头检查链表，确保移除后新出现的重复段被处理。
• 重复段移除：找到连续重复的起始节点后，遍历到段的末尾，直接将前一个节点的next指向段末尾的下一个节点，完成整个段的移除。

示例验证 #

• [1,2,2,3,3,1] → 移除2,2→[1,3,3,1] → 移除3,3→[1,1] → 移除1,1→[]，返回0，符合预期。
• [1,2,3,4,5,6]：无重复段，返回6。
• [1,2,3,2,2,1]：移除2,2→[1,2,3,1]，返回4。

规则2：保留连续重复节点的第一个，移除其余（示例4匹配） #

规则说明：找到最左侧的连续重复节点，移除后续重复节点（保留第一个）；重复此操作直到没有连续重复对为止。

修改后的代码 #

public int remainingNodes() {
    if (start == null) return 0;

    Node dummy = new Node(-1);
    dummy.next = start;
    Node prev = dummy;
    Node curr = start;
    boolean hasDuplicates;

    do {
        hasDuplicates = false;
        while (curr != null && curr.next != null) {
            if (curr.value == curr.next.value) {
                hasDuplicates = true;
                // 移除后续所有重复节点，保留当前节点
                while (curr.next != null && curr.value == curr.next.value) {
                    curr.next = curr.next.next;
                }
                prev = curr;
                curr = curr.next;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        // 重新从头检查新形成的重复
        prev = dummy;
        curr = dummy.next;
    } while (hasDuplicates);

    // 统计剩余节点数
    int count = 0;
    curr = dummy.next;
    while (curr != null) {
        count++;
        curr = curr.next;
    }
    start = dummy.next;
    return count;
}

示例验证 #

• [1,2,2,2,3,1] → 移除后两个2→[1,2,3,1]，返回4，符合预期。
• [1,2,3,2,2,1] → 移除两个2→[1,2,3,1]，返回4。

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