精华内容
下载资源
问答
  • 给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ...
    给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。有环链表的定义:在链表中某个节点的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一次移动一步。这就好比两辆赛车绕着同一条赛道以不同的速度前进,最终必然会碰到一起。

    聪明的读者可能会问: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;
    }


    展开全文
  • 有环链表监测方法

    2019-10-06 22:27:27
    文章目录有环链表检测链表是否环的两种方法 有环链表 检测链表是否环的两种方法 第一种快慢指针法 ​ 快慢指针法,每次走一步,另外一个指针每次走两步,或者更多,当两个指针能够指向同一个位置的时候,说明...

    有环链表

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

    循环链表示例图

                +-------------------------------------------------+
                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课 循环链表循环链表循环链表的建立与展示约瑟夫环判断有环链表 循环链表 只要将链表的两头相连,使其成为了一个环状链表,通常称之为循环链表 需要注意的是,虽然循环链表成环状,但本质上...

    数据结构个人笔记 第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;
    }
    

    判断有环链表

    也即判断一个链表中是否有环

    1. 这种问题常用快慢指针来解决,也即慢指针每走一步,则快指针走两步,一直走下去。如果链表中有环,快慢指针一定会在环中碰到,如果碰到就输出true,没有则false
    2. 从这个问题扩展出,环的入口在哪,环内有几个节点,链表一共有几个节点

    在有环链表的输出中,因为要遍历整个链表,所以我们可以用遍历的方法检测所有点的地址是否相同来判断是否有环,也可以用哈希表的方法来判断。
    如果使用快慢指针来解决问题,慢指针每向前走一步,快指针走两步,因此当慢指针进入环后,每一次操作都会使得快指针到慢指针的距离缩短一步,这样继续下去会使得两者之间的距离逐渐缩小,直到相遇,又因为在同一个环内,所以两者之间的距离不会大于环的长度,因此到两者相遇为止,慢指针一定还没走完一圈

    从上面可知,当快慢指针相遇时,慢指针一定还没走完链表,假设快指针已经在环内循环了n圈(1<=n)。假设慢指针走了s步,则快指针走了2s步,又由于快指针走过的步数为s+nr,则可以得出下面这个等式:
    2
    s = 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;
    }
    
    

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

    展开全文
  • 如何检测一个链表是否环的链表: 环的链表是指链表环路,例如A-&amp;gt;B-&amp;gt;C-&amp;gt;D-&amp;gt;E-&amp;gt;F-&amp;gt;B,遍历的时候B-&amp;gt;C-&amp;gt;D-&...
  • 如何检测一个单链表中是否环,例如下图的例子。 解决思路1:快慢指针法 这是最常见的方法。思路就是两个指针P1和P2,同时从头结点开始往下遍历链表中的所有节点。 P1是慢指针,一次遍历一个节点。 P2是快...
  • 给你一个链表的头节点 head ,判断链表中是否环。 如果链表中存在环,则返回 true 。 否则,返回 false 。 使用 HashSet 判断,简单办法 public boolean hasCycle(ListNode head) { // 空间法(不符合题意,题意...
  • 示例 1: 输入:19 输出:true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 示例 2: 输入:n = 2 输出:false 哈希集合检测循环 class Solution { public boolean isHappy(int n) { Set...
  • 【题目描述】Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using ... 环链表:从判断一个单链表是否存在循环而扩展衍生的问题,则称之为有环链表问题。 【解决
  • [寻找环链表入口点] 快慢指针数学原理剖析

    千次阅读 多人点赞 2018-12-02 14:25:25
    链表环路检测及环入口定位是一个非常经典的算法问题,它可在死锁检测等实际应用场景发挥重要作用。想必大家都知道这个问题应该使用快慢指针去求解,因为它具有最优的时间复杂度O(n)。但是大家可能对快慢指针的数学...
  • 给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 题目解答 1.快慢指针只能检测是否环,结果是...
  • //创建有环链表 cout; cin >> nLen; CreateList(&pHeadSec,nLen); CreateCrossingList(pHeadFirst,pHeadSec); bIsCircle = IsCrossing(pHeadFirst,pHeadSec); if (bIsCircle) { cout相交!"; } else { ...
  • 链表环状检测主要三种方法: 1、追赶法;如 robinzsy。 2、外部记录法;如improgrammer。 3、内部记录法(打记号);如VivianSnow。 内部标记法和外部标记法其实是一个道理,不过就是辅助变量一个是...
  • 题目:给定两个单链表(first, second),检测两个链表是否交点,如果返回第一个交点。 思路: 如果first==second,那么显然相交,直接返回first。 否则,分别从first,second开始遍历两个链表获得其长度len1与len2...
  • 链表算法--检测

    2018-11-14 08:46:06
    给定一个单链表,判断其中是否环,已经是一个比较老同时也是比较经典的问题,在网上搜集了一些资料, 然后总结一下大概可以涉及到的问题,以及相应的解法。   首先,关于单链表中的环,一般涉及到一下问题: ...
  • 1、检测链路是否存在环路。通过FastRunner/SlowRunner法,FastRunner一次移动两步,SlowRunner一次移动一步。 2、当二者碰到之后,F继续走,S从头走。当他们再次碰头时,那就是环的入口。 建议:空想好难,建议...
  • 给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = ...
  • 如何判断链表

    千次阅读 2019-03-11 10:26:57
    如何判断单链表是否存在环 ...如何用程序判断出这个链表是有环链表? 不允许修改链表结构。 时间复杂度O(n),空间复杂度O(1)。 方法一、穷举遍历 方法一:首先从头节点开始,依次遍历单链表的每...
  • 最初有环链表  2.反转 一 明白人会发现,此时并不算反转完成 3.反转 二   可见,环路的链表,反转过后sentinel位置不变,因此可以通过反转链表,凭借sentinel位置是否改变来检测是否...
  • 就如数字6一样的单链表结构,如何检测是否6下部的○呢,并且求交叉点位置 思路 使用快慢指针(一个一次走2步,一个走1步),若快慢指针第一次相遇,则环 慢指针路程 s = a+b 快指针路程 2s = a+b+nR s = nR ...
  • /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* detectCycle(ListNode* head) { ListN...
  • 链表环路检测

    2020-07-22 10:22:28
    检测有没有环,使用快慢指针slow和fast(一次走两步); 2.找位置,当找到环之后,slow从head出发,fast从相遇点出发,一次都走一步,再次相遇为环的入口点 public class detectCycle { pu.
  • 一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。 二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们...
  • 检测链表是否

    2017-04-07 19:15:41
    1. 如何检测一个链表是否环具体步骤 2. 如何找到环的入口点
  • 算法之链表环路检测

    2020-06-28 09:30:10
    给定一个有环链表,实现一个算法返回环路的开头节点。 环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [1,2,3,4], pos = 1 输出:tail ...
  • 1.6 如何检测一个较大的单链表是否环 【阿里巴巴笔试题】 难度系数:⭐⭐⭐⭐ 考察频率:⭐⭐⭐⭐⭐ 题目描述: 单链表环指的是单链表中某个结点的next域指向的是链表中它之前的某一个结点,这样在链表的尾部...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 817
精华内容 326
关键字:

有环链表检测