给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。有环链表的定义：在链表中某个节点的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;
}

 

 

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

 
有环链表
 
代码地址数据结构代码仓库
 
循环链表示例图
 
            +-------------------------------------------------+
            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);
        }
    }

}

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

 
数据结构个人笔记 第8课 循环链表
 
循环链表
循环链表的建立与展示
约瑟夫环
判断有环链表
 

 
循环链表
 
只要将链表的两头相连，使其成为了一个环状链表，通常称之为循环链表
 
 需要注意的是，虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元结点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样
 
循环链表的建立与展示
 
在建立循环链表时，就比建立普通链表多一个尾指针指向第一个节点。
 
person * initPerson(int num){
	person * head = (person *)malloc(sizeof(person));
	head -> data = 1;
	head -> next = NULL;
	person * temp = head;
	for(int i = 2;i<=num;i++){
		person * body = (person *)malloc(sizeof(person));
		body -> next =NULL;
		body -> data = i;
		temp -> next = body;
		temp = temp -> next;
	}
	temp -> next = head;
	return head;
}
 
在display循环链表时，不能用之前的尾指针指向NULL来判定链表结束了，需判定尾指针指向的是头节点，才算是结束
 
void display(person * head){
	person * temp = head;
	while(temp){
		printf("%d ",temp -> data);
		temp = temp -> next;
		if(temp== head){
			printf("\n");
			break;
		}
	}
}
 
约瑟夫环
 
也即，已知n个人（分别编号1,2，3，。。。。，n表示）围坐在一张圆桌旁，从编号为k开始顺时针报数，数到m的那个人出列；他的下一个人又从1开始，还是顺时针开始报数，数到m的那个人又出列，依次重复下去，知道圆桌剩余一个人。
 
完整代码：
 
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	struct node * next;
	int data ;
}person;

person * initPerson(int num){
	person * head = (person *)malloc(sizeof(person));
	head -> data = 1;
	head -> next = NULL;
	person * temp = head;
	for(int i = 2;i<=num;i++){
		person * body = (person *)malloc(sizeof(person));
		body -> next =NULL;
		body -> data = i;
		temp -> next = body;
		temp = temp -> next;
	}
	temp -> next = head;
	return head;
}

void display(person * head){
	person * temp = head;
	while(temp){
		printf("%d ",temp -> data);
		temp = temp -> next;
		if(temp== head){
			printf("\n");
			break;
		}
	}
}

void findKiller(person * head,int k, int m){
	person * temp = head;
	person * findK = head;
	while (findK -> data != k){
		findK = findK -> next;
	}
	temp = findK;
	while(findK -> next != findK){
		for(int i = 1;i<m;i++){
			temp = findK;
			findK = findK -> next;
		}
		temp -> next = findK -> next;
		printf("出列人的编号为%d\n",findK -> data);
		free(findK);
		findK = temp -> next;
	}
	printf("最后一个出列人的编号为%d\n",findK -> data);
	free(findK);
}

int main(){
	printf("请输入一共多少人\n");
	int num;
	scanf("%d",&num);
	person * head = initPerson(num);
	display(head);
	
	int k;
	scanf("%d",&k);
	printf("从第%d个人开始报数：\n",k);

	
	int m;
	scanf("%d",&m);
	printf("数数到%d的人出列：\n",m);

	
	findKiller(head,k,m);
	
	return 0;
}
 
判断有环链表
 
也即判断一个链表中是否有环
 
这种问题常用快慢指针来解决，也即慢指针每走一步，则快指针走两步，一直走下去。如果链表中有环，快慢指针一定会在环中碰到，如果碰到就输出true，没有则false
从这个问题扩展出，环的入口在哪，环内有几个节点，链表一共有几个节点
 
在有环链表的输出中，因为要遍历整个链表，所以我们可以用遍历的方法检测所有点的地址是否相同来判断是否有环，也可以用哈希表的方法来判断。
 如果使用快慢指针来解决问题，慢指针每向前走一步，快指针走两步，因此当慢指针进入环后，每一次操作都会使得快指针到慢指针的距离缩短一步，这样继续下去会使得两者之间的距离逐渐缩小，直到相遇，又因为在同一个环内，所以两者之间的距离不会大于环的长度，因此到两者相遇为止，慢指针一定还没走完一圈
 
从上面可知，当快慢指针相遇时，慢指针一定还没走完链表，假设快指针已经在环内循环了n圈（1<=n）。假设慢指针走了s步，则快指针走了2s步，又由于快指针走过的步数为s+nr，则可以得出下面这个等式：
 2s = s+n*r —> s = n * r
 
如果假设整个链表的长度为L，入口和相遇点的距离是x，起点到入口有点的距离是a，则有：
 a + x = s= n* r;
 a + x = (n-1) * r + r = (n - 1) * r + (L - a)
 由环的长度 = 链表总长度 - 起点到入口点的距离求出：
 a = (n - 1) * + (L - a - x)
 
上面的所有问题都可以嵌套这些公式，于是总结代码为：
 
#include <stdio.h>
#include <stdlib.h>

typedef struct line{
	struct line * next;
	int data;
};

line * initLine(int num ,int data){
	line * head = (line *)malloc(sizeof(line));
	head -> data = 1;
	head -> next = NULL;
	line * temp = head;
	for(int i = 2 ; i <= data ;i++){
		line * body = (line *)malloc(sizeof(line));
		body -> data = i;
		body -> next =NULL;
		temp -> next = body;
		temp = temp -> next;
	}
	line * round = head;
	for(int i = 1;i < num;i++){
		round = round -> next;
	}
	temp -> next = round;
	return head;
}

void display(line * head){
	line * temp = head;
	int i = 0;
	while(temp){
		printf("%d ",temp -> data);
		temp = temp -> next;
		i++;
		line * round = head;
		for(int j = 1;j< i ;j++){
			if(temp == round){
				printf("\n");
				return;
			} 
			round = round -> next; 
		}
	}
}

int checkRound(line * head){
	line * quick = head;
	line * slow = head;
	int i = 0;
	while(slow != NULL && quick -> next != NULL){
		i++;
		slow = slow -> next;
		quick = quick -> next -> next;
		if (slow == quick){
			printf("%d\n",i);
			break;
		}
	}
	line * ptr = head;
	while(slow != NULL && ptr != NULL){
		slow = slow -> next;
		ptr = ptr -> next;
		if(slow == ptr){
			return ptr -> data; 
		}
	}
	
}

int main(){
	line * head = initLine(28,30);
	display(head);
	
	printf("在链表中存在环,环的入口为：%d\n",checkRound(head));

	
	return 0;
}

 
这里只解决了判断入口的问题，其他的都可以以此类推
 参考资料：判断链表有环