链表Linked List-在给定的链表中查找循环/周期的长度Find length of loop/cycle in given Linked List(10)

Bertha 。 2023-09-24 20:23 26阅读 0赞

# 1.问题 #

给定链表的头部。任务是查找链表中是否存在循环，如果存在则返回链表中循环的长度，否则返回 0。

Examples:  
![在这里插入图片描述][a363a4f5880249bbb13fff549aa7cfaa.png]

> Input: linked list =  
> Output: 4  
> Explanation: The loop is present in the below-linked list and the length of the loop is 4.

> Input: linked list = 4 -> 3 -> 7 -> 9 -> 2  
> Output: 0

# 2.解决方法 #

## 使用弗洛伊德循环检测算法 ##

### 解题思路 ###

当快指针和慢指针在公共点相遇时，Floyd 循环检测算法终止。还已知该公共点是循环节点之一。将这个公共点的地址存储在一个指针变量ptr中。然后用1初始化一个计数器，并从公共点开始，继续访问下一个节点并增加计数器，直到再次到达公共指针。此时，计数器的值将等于循环的长度。

1.  使用弗洛伊德循环检测算法查找循环中的公共点
2.  将指针存储在临时变量中并保持计数 = 0
3.  遍历链表直到再次到达相同的节点并在移动到下一个节点时增加计数。
4.  将计数打印为循环长度

static int countNodes(ListNode n){
        
            int rest=1;//1.初始值的个数为1，链式变量
            ListNode temp=n;
            while(temp.next!=n){
        
                rest++;
                temp=temp.next;
            }
            return rest;
        }
        static int countNodesInLoop(ListNode head){
        
            ListNode slow=head,fast=head;//1.快慢指针找到公共点相遇
            while(slow!=null&&fast!=null&&fast.next!=null){
        
                fast=fast.next.next;
                slow=slow.next;
                if(slow==fast){
        //2.如果公共点相遇的两个值相等，则进入countNodes(slow)，计算循环的个数，否者没有循环返回0
                    return countNodes(slow);
                }
            }
            return 0;
        }

### 代码 ###

package com.Amy.leecode;
    
    import java.util.List;
    
    class LinkedList {
        
        static ListNode head;
        static int countNodes(ListNode n){
        
            int rest=1;
            ListNode temp=n;
            while(temp.next!=n){
        
                rest++;
                temp=temp.next;
            }
            return rest;
        }
        static int countNodesInLoop(ListNode head){
        
            ListNode slow=head,fast=head;
            while(slow!=null&&fast!=null&&fast.next!=null){
        
                fast=fast.next.next;
                slow=slow.next;
                if(slow==fast){
        
                    return countNodes(slow);
                }
            }
            return 0;
        }
    
        public static void main(String[] args) {
        
    
            ListNode head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(3);
            head.next.next.next = new ListNode(4);
            head.next.next.next.next = new ListNode(5);
            head.next.next.next.next.next = head.next;
            System.out.println(countNodesInLoop(head));
        }
    
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

### 运行结果 ###

[a363a4f5880249bbb13fff549aa7cfaa.png]: https://img-blog.csdnimg.cn/a363a4f5880249bbb13fff549aa7cfaa.png