循环双向链表大小的递归计算方法

聖光之護 2025-08-02 00:00:00 次阅读

循环双向链表是一种特殊的链表结构，其尾节点指向头节点，形成一个环。在计算循环双向链表的大小时，传统的遍历方法需要特别注意避免无限循环。本文介绍一种使用递归方法来解决此问题的方案。

递归计算链表大小

直接使用给定的头节点进行递归判断可能会遇到问题，因为在递归过程中，头节点会不断变化，无法作为递归结束的判断依据。因此，我们需要引入一个辅助函数，记录起始节点，并与当前节点进行比较，从而避免无限循环。

以下是具体的实现代码：

public class CircularDoublyLinkedList {

    private static class ListNode {
        int element;
        ListNode next;
        ListNode prev;

        ListNode(int element) {
            this.element = element;
        }
    }

    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("The size of the circular doubly linked list is: " + size); // 输出：3
    }
}

代码解释:

size(ListNode head) 方法: 此方法是公开的入口点，接收链表的头节点作为参数。如果头节点为空，则链表为空，返回 0。否则，调用私有的 recursiveSize 方法进行递归计算，并将头节点的下一个节点和头节点本身作为参数传递。
recursiveSize(ListNode current, ListNode start) 方法: 此方法是递归的核心。它接收当前节点 current 和起始节点 start 作为参数。
- 递归结束条件: 如果 current 等于 start，说明已经绕回到了链表的起始位置，递归结束，返回 0。
- 递归步骤: 否则，返回 1（表示当前节点）加上递归调用 recursiveSize 的结果，将 current 的下一个节点和 start 节点作为参数传递。