递归计算双向链表长度方法

本文介绍了一种使用递归方法计算循环双向链表大小的有效方案。循环双向链表的特点是其最后一个节点指向头节点，形成一个环。由于其特殊性，直接使用 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
    }
}

代码解释：

1. size(ListNode head) 方法： 这是公开的入口方法，接收链表的头节点作为参数。如果头节点为空，则链表为空，返回 0。否则，调用 recursiveSize 方法开始递归计数，初始计数为1（因为头节点存在）。

2. recursiveSize(ListNode current, ListNode start) 方法： 这是递归的核心方法，接收当前节点 current 和起始节点 start 作为参数。

   • 终止条件： 当 current 等于 start 时，表示已经遍历回到起始节点，完成了一个循环，递归结束，返回 0。
   • 递归调用： 否则，计数加 1，并递归调用 recursiveSize 方法，将 current.next 作为新的当前节点，start 保持不变。

注意事项：

• 避免无限循环： 关键在于 recursiveSize 方法中的终止条件 current == start。通过比较当前节点和起始节点，可以有效地检测到循环的结束，避免无限递归。
• 空链表处理： size(ListNode head) 方法中对 head == null 的判断是必要的，用于处理空链表的情况。
• 起始节点保存： recursiveSize 方法需要保存起始节点的信息，以便在递归过程中进行比较。

总结：

使用递归方法计算循环双向链表的长度需要特别注意避免无限循环。通过传递起始节点信息并在递归过程中进行比较，可以有效地解决这个问题。上述代码提供了一个清晰、简洁的解决方案，可以准确地计算循环双向链表的长度。