文章目录
有环链表
循环链表示例图
检测链表是否有环的两种方法

有环链表
代码地址数据结构代码仓库
循环链表示例图
            +-------------------------------------------------+
            v                                                 |
+---+     +---+     +---+     +---+     +---+     +---+     +---+
| 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 | --> | 6 | --> | 7 |
+---+     +---+     +---+     +---+     +---+     +---+     +---+

检测链表是否有环的两种方法
第一种快慢指针法
​	快慢指针法，每次走一步，另外一个指针每次走两步，或者更多，当两个指针能够指向同一个位置的时候，说明链表中存在环。
// 利用快慢指针的方法
int HasLoop2(LinkList L)
{
    LinkList p = L;
    LinkList q = L;

    while (p != NULL && q != NULL && q->next != NULL)
    {
        p = p->next;
        if (q->next != NULL)
            q = q->next->next;

        printf("p:%d, q:%d \n", p->data, q->data);

        if (p == q)
            return 1;
    }
    return 0;
}

第二种比较步数法
​	一个指针每次向前走一步，走的次数为n，另一个指针每次从头开始向前走(最多走n步)，当两个指针指向同一个位置的时候，但是第二个指针走的步数小于n(或者说不等于n)，这时说明链表中存在环
// 比较步数的方法
int HasLoop1(LinkList L)
{
    LinkList cur1 = L;  // 定义结点 cur1
    int pos1 = 0;       // cur1 的步数

    while(cur1)
    {                       // cur1 结点存在
        LinkList cur2 = L;  // 定义结点 cur2
        int pos2 = 0;       // cur2 的步数
        while(cur2)
        {                           // cur2 结点不为空
            if(cur2 == cur1)
            {                       // 当cur1与cur2到达相同结点时
                if(pos1 == pos2)    // 走过的步数一样
                    break;          // 说明没有环
                else                // 否则
                {
                    printf("环的位置在第%d个结点处。\n\n", pos2);
                    return 1;       // 有环并返回1
                }
            }
            cur2 = cur2->next;      // 如果没发现环，继续下一个结点
            pos2++;                 // cur2 步数自增
        }
        cur1 = cur1->next;  // cur1继续向后一个结点
        pos1++;             // cur1 步数自增
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node, *LinkList;

/* 初始化带头结点的空链表 */
Status InitList(LinkList *L);

/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkList L);

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n);

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n);

// 利用快慢指针的方法
int HasLoop2(LinkList L);

int HasLoop1(LinkList L);

/* 初始化带头结点的空链表 */
Status InitList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */

    if(!(*L)) /* 存储分配失败 */
            return ERROR;
    //< 初始化的首节点，指向为NULL的数据
    (*L)->next=NULL; /* 指针域为空 */

    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一个结点 */
    while(p)
    {
        i++;
        p=p->next;
    }
    return i;
}

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
	LinkList p;
	int i;

	srand(time(0));                         /*  初始化随机数种子 */

	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                      /*  建立一个带头结点的单链表 */

	for (i=0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;             /*  随机生成100以内的数字 */
		p->next = (*L)->next;               /* 新申请的节点放到老节点之前 */
		(*L)->next = p;						/*  插入到表头 */
	}
}

/*
       ┌──────────────────────────┬───────────────┬─────────┐
       │Interface                 │ Attribute     │ Value   │
       ├──────────────────────────┼───────────────┼─────────┤
       │rand(), rand_r(), srand() │ Thread safety │ MT-Safe │
       └──────────────────────────┴───────────────┴─────────┘
*/
/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
	LinkList p,r;
	int i;

	srand(time(0));                      /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
	r = *L;                              /* r为指向尾部的结点 */

	for (i=0; i < n; i++)
	{
		p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;           /*  随机生成100以内的数字 */
		r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
		r = p;                            /* 将当前的新结点定义为表尾终端结点 */
	}

    //< 生成循环链表，将尾节点指向第二个节点 (*L)->next->next
    r->next = (*L)->next->next;
}

// 比较步数的方法
int HasLoop1(LinkList L)
{
    LinkList cur1 = L;  // 定义结点 cur1
    int pos1 = 0;       // cur1 的步数

    while(cur1)
    {                       // cur1 结点存在
        LinkList cur2 = L;  // 定义结点 cur2
        int pos2 = 0;       // cur2 的步数
        while(cur2)
        {                           // cur2 结点不为空
            if(cur2 == cur1)
            {                       // 当cur1与cur2到达相同结点时
                if(pos1 == pos2)    // 走过的步数一样
                    break;          // 说明没有环
                else                // 否则
                {
                    printf("环的位置在第%d个结点处。\n\n", pos2);
                    return 1;       // 有环并返回1
                }
            }
            cur2 = cur2->next;      // 如果没发现环，继续下一个结点
            pos2++;                 // cur2 步数自增
        }
        cur1 = cur1->next;  // cur1继续向后一个结点
        pos1++;             // cur1 步数自增
    }
    return 0;
}

// 利用快慢指针的方法
int HasLoop2(LinkList L)
{
    LinkList p = L;
    LinkList q = L;

    while (p != NULL && q != NULL && q->next != NULL)
    {
        p = p->next;
        if (q->next != NULL)
            q = q->next->next;

        printf("p:%d, q:%d \n", p->data, q->data);

        if (p == q)
            return 1;
    }
    return 0;
}

int main()
{
    LinkList L;

    char opp;
   

    InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));

    printf("\n1.创建有环链表（尾插法） \n2.创建无环链表（头插法） \n3.判断链表是否有环 \n0.退出 \n\n请选择你的操作：\n");
    while(opp != '0')
    {
        scanf("%c",&opp);
        switch(opp)
        {
            case '1':
                CreateListTail(&L, 7);
                printf("成功创建有环L(尾插法)\n");
                printf("\n");
                break;

            case '2':
                CreateListHead(&L, 7);
                printf("成功创建无环L(头插法)\n");
                printf("\n");
                break;

            case '3':
                printf("方法一: \n\n");
                if( HasLoop1(L) )
                {
                    printf("结论：链表有环\n\n\n");
                }
                else
                {
                    printf("结论：链表无环\n\n\n");
                }

                printf("方法二：\n\n");
                if( HasLoop2(L) )
                {
                    printf("结论：链表有环\n\n\n");
                }
                else
                {
                    printf("结论：链表无环\n\n\n");
                }
                printf("\n");
                break;

            case '0':
                exit(0);
        }
    }

}


代码地址数据结构代码仓库

题目：
给定两个非环单链表(first, second)，检测两个链表是否有交点，如果有返回第一个交点。
 
思路：
如果first==second,那么显然相交，直接返回first。
否则，分别从first,second开始遍历两个链表获得其长度len1与len2。假设len1>len2，那么指针p1由first开始向后移动len1-len2步。
指针p2=second，下面p1、p2每次向后前进一步并比较是否相等，如果相等即返回该结点，否则说明两个链表没有交点。
 
代码：
Node *IsIntersect(Node *first, Node *second)
{
    if(first == NULL || second == NULL)
    {
        return NULL;
    }
    Node *p1, *p2;
    p1 = first;
    p2 = second;
    int len1 = Length_LinkList(first);
    int len2 = Length_LinkList(second);
    if(len1 >= len2)
    {
        for(int i = 0; i < len1-len2; i++)
        {
            p1 = p1->next;
        }
    }else
    {
        for(int i = 0; i < len2-len1; i++)
        {
            p2 = p2->next;
        }
    }
    while(p1 != NULL && p2 != NULL)
    {
        if(p1 == p2)
        {
            return p1;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return NULL;
}
注：代码中所用到的计算单链表长度的Length_LinkList()函数请看“单链表基础”
 
扩展：考虑假设链表有环，应该怎么检测是否有交点？

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
示例 1：
输入：head = [3,2,0,-4], pos = 1

输出：tail connects to node index 1

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

输出：tail connects to node index 0

解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1

输出：no cycle

解释：链表中没有环。
进阶：

你是否可以不用额外空间解决此题？
思路图解:

代码实现：
/**
 * 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) {
        //慢行指针slow
        ListNode slow = head;
        //快行指针fast
        ListNode fast = head;
        
        //在一个环上，看做谁追谁不是绝对的
        while (true) {
            //若没有环，fast的最终指向会为空
            if (fast == null || fast.next == null) {
                //无环直接返回空
                return null;
            }
            //慢行指针步进1
            slow = slow.next;
            //快行指针步进2
            fast = fast.next.next;
            
            //相遇则暂停
            if (slow == fast) {
                break;
            }
        }
        
        //p即为图解中指向原点O的指针
        //图解中指向P的指针还是slow
        ListNode p = head;
        while (p != slow) {
            //两者步进都为1走向图解中的A点
            p = p.next;
            slow = slow.next;
        }
        //循环退出时即同时到达A点
        //返回图解A处的结点即为答案
        return p;
    }
}

检测链表是否存在环路
有一种简单的做法叫FastRunner/SlowRunner法。FastRunner一次移动两步，而SlowRunner一次移动一步。这就好比两辆赛车绕着同一条赛道以不同的速度前进，最终必然会碰到一起。
聪明的读者可能会问：FastRunner会不会刚好“越过”SlowRunner，而不发生碰撞呢？绝无可能。假设FastRunner真的越过了SlowRunner，且SlowRunner处于位置i，FastRunner位于位置i+1。那么，在前一步，SlowRunner就处于位置i-1，FastRunner处于位置((i+1)-2)或i-1。也就是说，两者碰在一起了。
 
什么时候碰在一起？
假定这个链表有一部分不存在环路，长度为k。
若运用上述算法，FastRunner和SlowRunner什么时候会碰在一起呢？
我们知道，SlowRunner每走p步，FastRunner就会走2p步。因此，当SlowRunner走了k步进入环路部分时，FastRunner已走了总共2k步，进入环路部分已有2k-k步或k步。由于k可能比环路长度大得多，实际上我们应该把它写作mod(k, LOOP_SIZE)步，并用K表示。
对于之后的每一步，FastRunner和SlowRunner之间不是走远一步就是更近一步，具体要看观察的角度。也就是说，因为两者处于圆圈中，当A以远离B的方向走出q步时，同时也是向B更近了q步。综上，我们得出以下几点：
(1)SlowRunner处于环路中的0步位置；
(2)FastRunner处于环路中的K步位置；
(3)SlowRunner落后于FastRunner，相距K步；
(4)FastRunner落后于SlowRunner，相距LOOP_SIZE-K步；
(5)每过一个单位时间，FastRunner就会更接近于SlowRunner一步。
那么，两个节点什么时候相遇？若FastRunner落后于SlowRunner，相距LOOP_SIZE-K步，并且每经过一个单位时间，FastRunner就走近SlowRunner一步，那么，两者将在LOOP_SIZE-K步之后相遇。此时，两者与环路起始处相距K步，我们将这个位置称为CollisionSpot。
 
如何找到环路起始处？
现在我们知道CollisionSpot与环路起始处相距K个节点。由于K=mod(k, LOOP_SIZE)(或者换句话说，k=K+M*LOOP_SIZE，其中M为任意整数)，也可以说，CollisionSpot与环路起始处相距k个节点。例如，若有个环路长度为5个节点，有个节点N处于距离环路起始处2个节点的地方，我们也可以换个说法：这个节点处于距离环路起始处7个、12个甚至397个节点。
至此，CollisionSpot和LinkedListHead与环路起始处均相距k个节点。
现在，若用一个指针指向CollisionSpot，用另一个指针指向LinkedListHead，两者与LoopStart均相距k个节点。以同样的速度移动，这两个指针会再次碰在一起——这次是在k步之后，此时两个指针都指向LoopStart，然后只需返回该结点即可。
 
将全部整合在一起
总结一下，FastPointer的移动速度是SlowPointer的两倍。当SlowPointer走了k个节点进入环路时，FastRunner已进入链表环路k个节点。也就是说FastRunner和SlowRunner相距LOOP_SIZE-k个节点。
接下来，若SlowPointer每走一个节点，FastRunner就走两个节点，每走一次，两者的距离就会更近一个节点。因此，在走了LOOP_SIZE-k次后，它们就会碰在一起。这时两者距离环路起始处就有k个节点。
链表首部与环路起始处也相距k个节点。因此，若其中一个指针保持不变，另一个指针指向链表首部，则两个指针就会在环路起始处相会。
 
根据之前的4部分描述，就能直接导出下面的算法。
(1)创建两个指针：FastPointer和SlowPointer。
(2)SlowPointer每走一步，FastPointer就走两步。
(3)两者碰在一起时，将SlowPointer指向LinkedListHead，FastPointer保持不变。
(4)以相同速度移动SlowPointer和FastPointer，一次一步，然后返回新的碰撞处。
 
下面给出算法代码：

LinkedListNode findBegining(LinkedListNode head) {
	LinkedListNode slow = head;
	LinkedListNode fast = head;

	/*找出碰撞处，将处于链表中LOOP_SIZE-k步的位置*/
	while(fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
		if(slow == fast) { // 碰撞
			break;
		}
	}

	/*错误检查，没有碰撞处，也即没有回路*/
	if(fast == null || fast.next == null) {
		return null;
	}

	/*将slow指向首部，fast指向碰撞处，两者距离环路
	 *起始处k步，若两者以相同速度移动，则必定会在环
	 *路起始处碰在一起*/
	slow = head;
	while(slow != fast) {
		slow = slow.next;
		fast = fast.next;
	}

	/*至此两者均指向环路起始处*/
	return fast;
}