本文共 2532 字，大约阅读时间需要 8 分钟。

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：返回索引为 0 的链表节点

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：返回 null

解释：链表中没有环。

回顾之前的 对其判断是否有环的代码

/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {
       public boolean hasCycle(ListNode head) {
           if(head==null || head.next == null) {
   			return false;		}		ListNode low = head;		ListNode fast = head;		while(fast.next!=null && fast.next.next!=null ) {
   			fast = fast.next.next;			low = low.next;            if(low==fast) {
   				return true;			}		}		return false;    }}

题解一、快慢指针来解题

class ListNode{
   		int val;		ListNode next;		ListNode(int x){
   			val = x;			next = null;		}	}		public class Solution {
   	    public ListNode detectCycle(ListNode head) {
   	        if(head==null || head.next==null) {
   	        	return null;	        }	    	// 快慢指针	    	ListNode low = head;	    	ListNode fast = head.next;	    	while(low!=fast) {
   	    		if(low.next==null || fast.next.next==null) {
   	    			return null;	    		}	    		low = low.next;	    		fast = fast.next.next;	    	}	    	fast = head;	    	while(low!=fast) {
   	    		low = low.next;	    		fast = fast.next;	    	}	    	return low;	    }	}

题解二、通过hashset来判断

/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {
       public ListNode detectCycle(ListNode head) {
           if(head==null || head.next==null){
               return null;        }        // 用hashset        HashSet
   
     hashSet = new HashSet<>();        hashSet.add(head);        while(head!=null){
               head = head.next;            if(hashSet.contains(head)){
                   return head;            }            hashSet.add(head);        }        return null;    }}
   

引申：两个单链表相交的情况，先要判断其是否有环。

若是两个无环的单链表，存在两个情况，一种是相交，另外一种是不相交；通过hashset来做即可。

一个有环一个无环，必不可能相交。

两个都有环，则是以下三种情况：

有环情况，进行判断 判断环的位置是否相同，如果相同，则用hashset来做即可。

有环情况，如果位置不相同，

cur1 = loop1.next;			while(cur1!=loop1) {
   				if(cur1==loop2) {
   					return loop1;				}				cur1 = cur1.next;			}			return null;

转载地址：https://codingchaozhang.blog.csdn.net/article/details/110454605 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！