判断单向链表是否有环，可以采用快指针与慢指针两个指针的方式来解决。即定义一个快指针fast和一个慢指针slow，使得fast每次跳跃两个节点，slow每次跳跃一个节点。如果链表没有环的话，则slow与fast永远不会相遇（这里链表至少有两个节点）；如果有环，则fast与slow将会在环中相遇。判断出链表有环以后，则需要算出进入环的第一个节点。在fast与slow第一次相遇后，设置一个节点p从链表的头部开始遍历，每次只遍历一个节点。这样，当fast与slow再次相遇时，p所处的位置便是环的首部。
 
1.判断一个单链表是否有环.
 
Public static boolean hasCycle(listNode head) {

    boolean flag = false;
    ListNode fast = head;
    ListNode slow = head;
    
    while(fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    
    if(fast == slow){
    flag = true;
    break;
    }
    return flag;
}
 
2.判断一个单链表中是否有环，若有环，求进入环中的第一个节点.
 
Public ListNode getFirstNodeInCycle(ListNode head) {

   if(head == null) {
   return null;
   } else {

   ListNode fast = head;
   ListNode slow = head;

   while(fast != null && fast.next != null) {
   
      slow = slow.next;
      fast = fast.next.next;
  
      if(fast == slow){
      
      //有环，则返回环的第一个节点
      slow = head;
      while(slow != fast){
      slow = slow.next;
      fast = fast.next;
      }
      return slow;
      }
  }
  return null;
  }
}
 
更多LeetCode解题

题目：如何判断一个单链表是否有环？若有环，如何找出环的入口节点。 
 一、单链表是否有环 
 思路分析： 
 单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。判断链表是否有环，有以下几种方法。
 
// 链表的节点结构如下
typedef struct node
{
    int data;
    struct node *next;
} NODE;
 
（1）最常用方法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。
 
// 判断链表是否有环
bool IsLoop(NODE *head) // 假设为带头节点的单链表
{
    if (head == NULL)
        return false;

    NODE *slow = head->next; // 初始时，慢指针从头节点开始走1步
    if (slow == NULL)
        return false;

    NODE *fast = slow->next; // 初始时，快指针从头节点开始走2步
    while (fast != NULL && slow != NULL) // 当单链表没有环时，循环到链表尾结束
    {
        if (fast == slow)
            return true;

        slow = slow->next; // 慢指针每次走一步

        fast = fast->next;
        if (fast != NULL)
            fast = fast->next;
    }

    return false;
}
 
（2）通过使用STL库中的map表进行映射。首先定义 map<NODE *, int> m; 将一个 NODE * 指针映射成数组的下标，并赋值为一个 int 类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，表示该节点第一次访问；而如果m[p]的值为1，则说明这个节点已经被访问过一次了，于是就形成了环。
 
#include <iostream>
using namespace std;
#include <map>

// 使用STL中的map来判断单链表中是否有环
map<NODE *, int> m;
bool IsLoop_2(NODE *head)
{
    if (head == NULL)
        return false;

    NODE *p = head;

    while (p)
    {
        if (m[p] == 0) // 一般默认值都是0
            m[p] = 1;
        else if (m[p] == 1)
            return true;

        p = p->next;
    }

     return false;
}
 
（3）不推荐使用：定义一个指针数组，初始化为空指针，从链表的头指针开始往后遍历，每次遇到一个指针就跟指针数组中的指针相比较，若没有找到相同的指针，说明这个节点是第一次访问，还没有形成环，将这个指针添加到指针数组中去。若在指针数组中找到了同样的指针，说明这个节点已经访问过了，于是就形成了环。
 
二、若单链表有环，如何找出环的入口节点。 
 步骤： 
 <1> 定义两个指针p1和p2，在初始化时都指向链表的头节点。 
 <2> 如果链表中的环有n个节点，指针p1先在链表上向前移动n步。 
 <3> 然后指针p1和p2以相同的速度在链表上向前移动直到它们相遇。 
 <4> 它们相遇的节点就是环的入口节点。 
 那么如何得到环中的节点数目？可使用上述方法（1），即通过一快一慢两个指针来解决这个问题。当两个指针相遇时，表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，即可得到环中的节点数了。
 
// 1、先求出环中的任一节点
NODE *MeetingNode(NODE *head) // 假设为带头节点的单链表
{
    if (head == NULL)
        return NULL;

    NODE *slow = head->next; // 初始时，慢指针从头节点开始走1步
    if (slow == NULL)
        return NULL;

    NODE *fast = slow->next; // 初始时，快指针从头节点开始走2步
    while (fast != NULL && slow != NULL) // 当单链表没有环时，循环到链表尾结束
    {
        if (fast == slow)
            return fast;

        slow = slow->next; // 慢指针每次走一步

        fast = fast->next;
        if (fast != NULL)
            fast = fast->next;
    }

    return NULL;
}

// 2、从已找到的那个环中节点出发，一边继续向前移动，一边计数，当再次回到这个节点时，就可得到环中的节点数了。
NODE *EntryNodeOfLoop(NODE *head)
{
    NODE *meetingNode = MeetingNode(head); // 先找出环中的任一节点
    if (meetingNode == NULL)
        return NULL;

    int count = 1; // 计算环中的节点数
    NODE *p = meetingNode;
    while (p != meetingNode)
    {
        p = p->next;
        ++count;
    }

    p = head;
    for (int i = 0; i < count; i++) // 让p从头节点开始，先在链表上向前移动count步
        p = p->next;

    NODE *q = head; // q从头节点开始
    while (q != p) // p和q以相同的速度向前移动，当q指向环的入口节点时，p已经围绕着环走了一圈又回到了入口节点。
    {
        q = q->next;
        p = p->next;
    }

    return p;
}
 
备注：在MeetingNode方法中，当快慢指针（slow、fast）相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n（n>=1）圈。假设slow指针走了s步，则fast指针走了2s步。同时，fast指针的步数还等于s加上在环上多转的n圈，设环长为r，则满足如下关系表达式： 
 2s = s + nr; 
 所以可知：s = nr; 
 假设链表的头节点到“环的尾节点“的长度为L（注意，L不一定是链表长度），环的入口节点与相遇点的距离为x，链表的头节点到环入口的距离为a，则满足如下关系表达式： 
 a + x = s = nr; 
 可得：a + x = (n - 1)r + r = (n - 1)r + (L - a) 
 进一步得：a = (n - 1)r + (L -a - x) 
 结论： 
 <1> (L - a -x)为相遇点到环入口节点的距离，即从相遇点开始向前移动(L -a -x)步后，会再次到达环入口节点。 
 <2> 从链表的头节点到环入口节点的距离 ＝ (n - 1) * 环内循环 ＋ 相遇点到环入口点的距离。 
 <3> 于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

这个问题可以两部分组成：
 
1、首席判读链表是否有环；
 
2、有环的话，在公共点拆开：设在ptr1 == ptr2 ，那么ptr2前进一步：ptr2 = ptr2->next;ptr1拆链表：ptr1->next = NULL;
 
此时，就有两个链表了：一个是原来的链表list1，在ptr1处结束;一个是以ptr1为头节点的新链表list2。于是问题转换成为了list1与list2的第一个公共节点。此问题已经解决。
 
代码实现如下：
 
# include <stdio.h>
# include <malloc.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList;
/**
 * 采用数组a[]来初始化链表，数组的长度为length;head指向了头节点。
 */
LinkList CreatList(int a[], int length)
{
	LinkList head = (LinkList)malloc(sizeof(LNode));
	head->next = NULL;
	int index;
	LinkList temp;
	for (index = 0; index < length; index ++)
	{
		temp = (LinkList)malloc(sizeof(LNode));
		temp->data = a[index];
		temp->next = head->next;
		head->next = temp;
	}
	return head;
}
/**
 * 判断链表list1与链表list2是否相交，如果相交的话，就返回第一个相交点
 * 注意相交的话，就是横着的Y字型
 */
int isIntersect(LinkList list1, LinkList list2)
{
	LinkList ptr1 = list1->next;
	LinkList ptr2 = list2->next;
	int len1 = getLength(list1);
	int len2 = getLength(list2);
	int step = len1 - len2;
	int index;
	if(step > 0)             //list1长，那么list1先走step；
	{
		for (index = 0; index < step; index ++)
			ptr1 = ptr1->next;
	}
	else					//list2长，那么list2先走step;
	{
		for (index = 0; index < -1 * step; index ++)
					ptr2 = ptr2->next;
	}
	while (ptr1 != NULL)
	{
		if (ptr1 == ptr2)
			{
				printf("the first intersection node is %d/n", ptr1->data);
				return 1;
			}
		ptr1 = ptr1->next;
		ptr2 = ptr2->next;
	}
	printf("there is no insection node between the two list");
	return 0;
}
/**
 *	如果链表有环，那么返回第一个入环的节点
 */
int getLoopNode(LinkList list)
{
	LinkList current = list->next;
	LinkList ptr1 = current;
	LinkList ptr2 = current;
	while (ptr2 != NULL)
	{
		ptr1 = ptr1->next;
//		ptr2 = ptr2->next->next;
		ptr2 = ptr2->next;
		if (ptr2 == NULL)
			return 0;
		else
			ptr2 = ptr2->next;
		if (ptr1 == ptr2)
			{
				ptr2 = ptr1->next;
				ptr1->next = NULL;
				LinkList begin = (LinkList)malloc(sizeof(LNode));   //begin为新链表，包含头节点；
				begin->next = ptr2;
				isIntersect(list, begin);
				return 1;
			}
	}
	return 0;
}
int main()
{
int a4[] = {1,2,3,4,5};
	LinkList list = CreatList(a4,5);
	LinkList current = list->next;
	while (current->next)
	{
		current = current->next;
	}
	current->next = list->next->next;   //一个环为4
        getLoopNode(list);
} 

 
文章目录
 
1.题目
2.分析:先判断链表是否成环(扩展:为什么快指针的速度是慢指针的两倍)
3.确定成环之后，如何找到入环节点
4.代码

 
1.题目
 
题目链接
 
 
2.分析:先判断链表是否成环(扩展:为什么快指针的速度是慢指针的两倍)
 
定义一个步伐为1的慢指针，一个步伐为2的快指针。如果链表成环，两者最终会相遇；
 如果没有相遇，则链表不成环；
 
 
3.确定成环之后，如何找到入环节点
 
 
4.代码
 
struct ListNode *detectCycle(struct ListNode *head) {
    //判断是否有环
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        break;
    }
    if(fast==NULL||fast->next==NULL)//无环
    return NULL;
    
    //有环，找节点
    struct ListNode *newhead=head;//从原点出发
    while(newhead!=fast)//一个从相遇点出发，一个从节点出发，相遇点即为入环点
    {
        newhead=newhead->next;
        fast=fast->next;
    }
    return fast;
}