环形链表判断

今天药忘吃喽~ 2024-04-06 11:29 50阅读 0赞

### 141. 环形链表 ###

> 给你一个链表的头节点 head ，判断链表中是否有环。

> 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

> 如果链表中存在环 ，则返回 true 。 否则，返回 false 。

##### 示例 1： #####

![在这里插入图片描述][bdd7514e1612460ea8b3c30d1abb4cc5.png]

> 输入：head = \[3,2,0,-4\], pos = 1  
> 输出：true  
> 解释：链表中有一个环，其尾部连接到第二个节点。

##### 示例 2： #####

![在这里插入图片描述][16249ea7efcb466aa488d0ae1d7a4115.png]

> 输入：head = \[1,2\], pos = 0  
> 输出：true  
> 解释：链表中有一个环，其尾部连接到第一个节点。

##### 示例 3： #####

![在这里插入图片描述][bf0a9b9e955a4e90abef41fcffb9d6c4.png]

> 输入：head = \[1\], pos = -1  
> 输出：false  
> 解释：链表中没有环。

##### 提示： #####

> 链表中节点的数目范围是 \[0, 104\]  
>  − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105  
> pos 为 -1 或者链表中的一个 有效索引 。

#### 代码（java）： ####

public class link_cycle {
        
    
    	 public static class ListNode {
        
    		
    	     int val;
    	     ListNode next;
    	     public ListNode(int x) {
        
    	         val = x;
    	         next = null;
    	    }
    	 }
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] h = {
        1};
    		int pos = -1;
    		ListNode head = new ListNode(h[0]);
    		ListNode p = null, q = null;
    		head.val = h[0];
    		p = head;
    		
    		if(pos == 0)
    			q = head;
    		for(int i = 1; i < h.length; i++) {
        
    			
    			ListNode l = new ListNode(h[i]);
    			p.next = l;
    			if(i == pos)
    				q = l;
    			p = p.next;
    		}
    		p.next = q;
    		System.out.println(hasCycle(head));
    	}
    	
    	public static boolean hasCycle(ListNode head) {
        
    		
    		if (head == null) {
        
    	        return false;
    	    }
    	    ListNode l1 = head, l2 = head.next;
    	    while (l1 != null && l2 != null && l2.next != null) {
        
    	        if (l1 == l2) {
        
    	            return true;
    	        }
    	        l1 = l1.next;
    	        l2 = l2.next.next;
    	    }
    	    return false;
            
        }
    
    }

##### 复杂度分析: #####

时间复杂度：O(N)，其中 N 是链表中的节点数。  
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。  
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N轮。

空间复杂度：O(1)。我们只使用了两个指针的额外空间。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

来源：[力扣（LeetCode）][LeetCode]  
注：仅供学习参考！

[bdd7514e1612460ea8b3c30d1abb4cc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2a9373ee55b5420a982cfb5cbb9e06f4.png
[16249ea7efcb466aa488d0ae1d7a4115.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/30011cfd215b4697baea6b62ae5359c8.png
[bf0a9b9e955a4e90abef41fcffb9d6c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8f52abc21d0f4b43b05cf27732723497.png
[LeetCode]: https://leetcode.cn/problems/linked-list-cycle