递归实现循环双向链表长度统计的问题求助

原方案的问题 #

你原来的思路通过修改节点元素标记已访问，存在两个致命问题：

• 彻底破坏链表原始数据，调用完size方法后所有节点的element都会被设为null，链表直接报废
• 如果链表中本身存在element为null的节点，会提前触发终止条件，导致计算结果错误

正确的递归实现思路 #

循环链表的终止条件是遍历回到起点，但主方法只能传入头节点，因此需要借助辅助递归方法，额外传递起始节点（原头节点）作为终止判断的依据，全程不修改链表任何数据。

代码实现 #

假设ListNode包含next双向指针：

public class Solution {
    public int size(ListNode head) {
        // 处理空链表场景
        if (head == null) {
            return 0;
        }
        // 初始计数包含头节点本身，后续从下一个节点开始递归
        return 1 + sizeHelper(head.next, head);
    }

    // 辅助递归方法：current为当前遍历节点，start为起始节点（原头节点）
    private int sizeHelper(ListNode current, ListNode start) {
        // 终止条件：回到起始节点，说明遍历完整个循环链表
        if (current == start) {
            return 0;
        }
        // 递归遍历下一个节点，累加计数
        return 1 + sizeHelper(current.next, start);
    }
}

逻辑说明 #

• 主方法先判断空链表，再以头节点为起点，初始计数+1（包含头节点），调用辅助方法遍历后续节点
• 辅助方法每次检查当前节点是否回到起始节点，是则终止递归返回0，否则继续递归并累加计数
• 全程不修改链表数据，完全保留原始结构；双向链表用current.next或current.prev遍历逻辑一致

边界情况覆盖 #

• 空链表：直接返回0
• 单节点循环链表：head.next指向自身，辅助方法直接返回0，最终结果为1，符合预期

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