当前位置：首页 > 文章列表 > 文章 > java教程 > 递归计算双向链表长度方法

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

2025-08-29 15:01:46 0浏览收藏

本文针对循环双向链表大小计算问题，提出了一种高效的递归解决方案。传统遍历方法在循环链表中易陷入无限循环，该文巧妙地利用递归，并引入辅助函数记录起始节点，与当前节点进行比较，有效避免了无限循环的发生。代码示例清晰展示了如何通过 `size(ListNode head)` 和 `recursiveSize(ListNode current, ListNode start)` 方法实现链表大小的递归计算。该方法不仅代码简洁易懂，而且保证了链表的完整性，为循环双向链表的操作提供了一种新的思路。了解更多关于循环链表大小计算的技巧，请继续阅读本文。

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

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

递归计算链表大小

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

以下是具体的实现代码：

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 节点作为参数传递。