Linked List-Detect loop in a linked list检测链表中的循环的4种方法(7)

刺骨的言语ヽ痛彻心扉 2023-09-24 20:11 6阅读 0赞

# 1. 问题 #

给定一个链表，检查链表是否有环。下图显示了带有循环的链表  
![在这里插入图片描述][917f38eaaee548838407592ad463e773.png]

# 2.解决方法 #

## 1）使用 Hashing 检测链表中的循环： ##

`时间复杂度：O(N)`，循环只需要遍历一次。  
`Auxiliary Space：O(N)`，N是在hashmap中存储值所需要的空间。

将节点插入哈希图中，每当遇到哈希图中已经存在的节点时，就返回 true。

1.  单独遍历列表并将节点地址放入哈希表中。
2.  在任何时候，如果达到 NULL，则返回 false
3.  如果当前节点中的下一个指向哈希中先前存储的任何节点，则返回 true。

public static boolean detectLoop(ListNode node){
        
            HashSet<ListNode> s = new HashSet<>();
            while(node!=null){
        
                if(s.contains(node)) return true;
                s.add(node);
                node=node.next;
            }
            return false;
    }

## 2)使用 Floyd 的循环查找算法检测链表中的循环 ##

算法用于在链表中查找循环。它使用两个指针，一个指针的移动速度是另一个指针的两倍。速度快的称为快指针，另一种称为慢指针。  
`时间复杂度：O(N)，循环只需要遍历一次。 辅助空间：O(1)。`

1.  使用两个指针遍历链表。
2.  将一个指针 (slow\_p) 移动一个，将另一个指针 (fast\_p) 移动两个。
3.  如果这些指针在同一节点相遇，则存在循环。如果指针不相交，则链表没有循环。  
    ![在这里插入图片描述][44d9a49ffeed47199ffbb8579b751180.png]

public boolean hasCycle(ListNode head) {
        
      ListNode slow = head, fast = head;//1.定义两个变量，分别为快和慢
      
      while (fast != null && fast.next != null) {
        //2.当最快的变量和最快变量下一个值不为null，slow为slow的next，fast为fast.next.next（Floyd 的循环查找算法）定义快慢指针,慢指针走一步,快指针走两步,若两者能相遇,则有循环
      //解释：快慢指针(双指针)法，快指针每次走两步，慢指针每次走一步；那么无环的情况下，快指针一定先到达终点；如果出现环，情况1：快指针回到慢指针之后的位置，那么快指针一定在某个时刻能追上慢指针，情况二：快指针回到慢指针之前的位置，那么快指针又会进入环，依次类推，总会回到慢指针后再追上慢指针；所以当快指针追上慢指针时，表示存在环；
    
    
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) //3.如果快慢相等，返回true；
            return true;
      }
      
      return false;//4.如果不相等为false
    }

## 3）通过修改值检测链表中的循环： ##

修改访问节点的值并检查当前节点值是否等于该值  
`时间复杂度：O(N) 辅助空间：O(1)`

1.  遍历链表并将该节点的值（数据）更改为-1。
2.  现在，在修改值之前检查节点的值是否已经是-1
3.  如果是 -1 则返回 TRUE 否则，更改节点的值。
4.  遍历链表直到到达 NULL。

public static boolean detectLoop(ListNode head){
        
            if(head==null||head.next==null) return false;
            while(head!=null) {
        
                if (head.val == -1) {
        
                 return true;
                }else{
        
                    head.val=-1;
                    head=head.next;
                }
            }
            return false;
        }

## 4)用递归检测链表中的循环： ##

1.如果head或者head.next为null（一个元素)，为false  
2.如果head.next = head,有循环，返回true  
3.用递归的方式调用detectLoop，求返回值

public static boolean detectLoop(ListNode head){
        
            if(head==null||head.next==null) return false;
            ListNode nextNode = head.next;
            head.next=head;
            boolean isCycle =detectLoop(nextNode);
            return isCycle;
        }

[917f38eaaee548838407592ad463e773.png]: https://img-blog.csdnimg.cn/917f38eaaee548838407592ad463e773.png
[44d9a49ffeed47199ffbb8579b751180.png]: https://img-blog.csdnimg.cn/44d9a49ffeed47199ffbb8579b751180.png