精华内容
下载资源
问答
  • 有环链表监测方法

    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);
            }
        }
    
    }
    
    

    代码地址数据结构代码仓库
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 题目:给定两个单链表(first, second),检测两个链表是否交点,如果返回第一个交点。 思路: 如果first==second,那么显然相交,直接返回first。 否则,分别从first,second开始遍历两个链表获得其长度len1与len2...

    题目:

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


    展开全文
  • 给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 题目解答 1.快慢指针只能检测是否有环,结果是...
  • 1、检测链路是否存在环路。通过FastRunner/SlowRunner法,FastRunner一次移动两步,SlowRunner一次移动一步。 2、当二者碰到之后,F继续走,S从头走。当他们再次碰头时,那就是环的入口。 建议:空想好难,建议...
  • 链表环路检测

    2020-07-22 10:22:28
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 链表有环理解:如果链表中有环,那么快慢指针就一定可以相遇,...
  • 定义两个指针fast、slow,其中,fast是快指针,slow是慢指针,二者的初始值都指向链表头, ... 否则,这个是不带环的链表(fast先行到达尾部为NULL,则为无环链表)。  代码:  public boolean IsL
  • 算法之链表环路检测

    2020-06-28 09:30:10
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [1,2,3,4], pos = 1 输出:tail ...
  • 链表的环路检测问题

    2020-07-28 15:52:04
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ...
  • 这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。 首先来看最基本的这个问题:如何判断一个单链表是否存在循环,链表数目未知。算法...
  • 给定一个有环链表,实现一个算法返回环路的开头结点。 思考: 第一:监测链表是否存在环路。有一种简单的方法叫做fastrunner/slowrunner法。fastruner一次移动两步,slowrunner一次移动一步。如果存在环路,最终...
  • 给定一个有环链表,实现一个算法返回环路的开头节点。 这个问题是由经典面试题-检测链表是否存在环路演变而来。
  • leetcode面试题 02.08. 环路检测

    千次阅读 多人点赞 2020-06-14 18:41:13
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ...
  • 环路检测

    2020-03-11 22:27:19
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ...
  • 02.08 环路检测

    2020-11-07 21:33:27
    给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ...
  • 力扣 环路检测

    2020-12-08 17:09:08
    给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到...
  • LeetCode:环路检测

    2020-07-30 20:12:04
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 2. 示例 输入:head = [3,2,0,-4], pos = 1 输出:tail ...
  • 给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ...
  • python:环路检测

    2020-08-22 00:33:15
    给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ...
  • 给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 我的解题 快慢指针 /** * Definition for singly-linked list...
  • 给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 /** * Definition for singly-linked list. * struct ...
  • Leetcode--环路检测

    2020-04-25 11:18:57
    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ...

空空如也

空空如也

1 2 3
收藏数 52
精华内容 20
关键字:

有环链表检测