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

花韻仙語 2025-08-02 00:00:00 次阅读

循环双向链表是一种特殊的链表结构，其尾节点指向头节点，形成一个环。在计算这种链表的长度时，传统的递归方法由于无法使用 null 作为终止条件而失效。本文将介绍一种通过引入辅助函数来解决此问题的递归方法。

核心思想

为了避免无限循环，我们需要一个明确的终止条件。由于不能修改原始方法的签名，我们引入一个私有的递归辅助函数，该函数接受当前节点和起始节点作为参数。当递归遍历回到起始节点时，递归终止。

实现步骤

主函数 size(ListNode head): 负责处理链表为空的情况，并调用递归辅助函数。
递归辅助函数 recursiveSize(ListNode current, ListNode start):
- 终止条件: 如果当前节点 current 等于起始节点 start，则表示已经遍历完整个链表，返回 0。
- 递归步骤: 否则，返回 1 加上对下一个节点 current.next 递归调用的结果，同时保持起始节点 start 不变。

代码示例

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 second = new ListNode(2);
        ListNode third = new ListNode(3);

        head.next = second;
        second.prev = head;
        second.next = third;
        third.prev = second;
        third.next = head;
        head.prev = third;

        CircularDoublyLinkedList list = new CircularDoublyLinkedList();
        int size = list.size(head);
        System.out.println("Size of the circular doubly linked list: " + size); // 输出: 3
    }
}