计算链表中环的长度

[!Tip]

本节源代码见Github链接🔗


问题描述

判定给定的链表是以NULL结尾,还是形成一个环。如果链表中存在环,返回环的长度


核心思路

通过Floyd环判定算法🔗来解决。主要包含以下4步:

  1. 定义两个指向链表头结点的指针slowPtr和fastPtr;
  2. 将两个指针按照不同的速度进行移动,如slowPtr每次向后移动1个结点,fastPtr每次向后移动2个结点;
  3. 若链表中存在环,slowPtr和fastPtr终将指向同一结点;若不存在环,fastPtr会先指向NULL;
  4. 确定存在环后,fastPtr停止不动,slowPtr继续移动,当两个指针再次相遇时,slowPtr移动的结点数即环的长度

计算链表中环的长度.png


实现代码

【👉🏻>>点击展开查看代码】
        
/**  
 * 计算链表中环的长度  
 *  
 * @author: Max Solider  
 * @date: 2022/10/9 14:18  
 * @param headNode  
 * @return int  
 */
 int findLoopLength(NormalListNode headNode) {  
    if (headNode == null || headNode.getNext() == null) {  
        return 0;  
    }  
    NormalListNode slowPtr = headNode, fastPtr = headNode;  
    boolean loopExists = false;  
    while (fastPtr.getNext() != null && fastPtr.getNext().getNext() != null) {  
        fastPtr = fastPtr.getNext().getNext();  
        slowPtr = slowPtr.getNext();  
        if (slowPtr == fastPtr) {  
            System.out.println("There is a loop in the linked list.");  
            loopExists = true;  
            break;        }  
    }  
    if (!loopExists) {  
        System.out.println("There is no loop in the linked list.");  
        return 0;  
    }  
    int loopLength = 1;  
    slowPtr = slowPtr.getNext();  
    while (slowPtr != fastPtr) {  
        slowPtr = slowPtr.getNext();  
        loopLength++;  
    }  
    System.out.println("The loop in the linked list has " + loopLength + " nodes");  
    return loopLength;  
}
        
    

时间复杂度

时间复杂度为O(n),用于遍历环。


空间复杂度

空间复杂度为O(1),用于存储临时变量。

© MaxSolider all right reserved,powered by Gitbook文件修订时间: 2022-10-12 23:29:02

results matching ""

    No results matching ""