本文介绍了一种使用递归方法计算循环双向链表大小的有效方案。循环双向链表的特点是其最后一个节点指向头节点，形成一个环。由于其特殊性，直接使用 null 检查无法确定链表的结尾。本文提供了一种通过传递起始节点信息来避免无限循环，从而准确计算链表长度的递归算法，并附带示例代码。
递归计算循环双向链表长度
循环双向链表是一种特殊的链表结构，其最后一个节点指向头节点，形成一个环。在计算这种链表的长度时，传统的遍历方法需要特别注意避免无限循环。递归方法提供了一种优雅的解决方案，但需要仔细设计以确保正确终止。
解决方案
以下代码展示了如何使用递归方法计算循环双向链表的长度：
public class CircularDoublyLinkedList {
static class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode(int val) {
this.val = val;
}
}
public int size(ListNode head) {
if (head == null) {
return 0;
}
return 1 + recursiveSize(head.next, head);
}
private int recursiveSize(ListNode current, ListNode start) {
if (current == start) {
return 0;
}
return 1 + recursiveSize(current.next, start);
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
head.next = node2;
node2.prev = head;
node2.next = node3;
node3.prev = node2;
node3.next = head;
head.prev = node3;
CircularDoublyLinkedList list = new CircularDoublyLinkedList();
int size = list.size(head);
System.out.println("Size of the circular doubly linked list: " + size); // Output: 3
}
}代码解释：
size(ListNode head) 方法： 这是公开的入口方法，接收链表的头节点作为参数。如果头节点为空，则链表为空，返回 0。否则，调用 recursiveSize 方法开始递归计数，初始计数为1（因为头节点存在）。
-
recursiveSize(ListNode current, ListNode start) 方法： 这是递归的核心方法，接收当前节点 current 和起始节点 start 作为参数。
- 终止条件： 当 current 等于 start 时，表示已经遍历回到起始节点，完成了一个循环，递归结束，返回 0。
- 递归调用： 否则，计数加 1，并递归调用 recursiveSize 方法，将 current.next 作为新的当前节点，start 保持不变。
注意事项：
- 避免无限循环： 关键在于 recursiveSize 方法中的终止条件 current == start。通过比较当前节点和起始节点，可以有效地检测到循环的结束，避免无限递归。
- 空链表处理： size(ListNode head) 方法中对 head == null 的判断是必要的，用于处理空链表的情况。
- 起始节点保存： recursiveSize 方法需要保存起始节点的信息，以便在递归过程中进行比较。
总结：
使用递归方法计算循环双向链表的长度需要特别注意避免无限循环。通过传递起始节点信息并在递归过程中进行比较，可以有效地解决这个问题。上述代码提供了一个清晰、简洁的解决方案，可以准确地计算循环双向链表的长度。
