精华内容
下载资源
问答
  • 判断单向链表是否有,可以采用快指针与慢指针两个指针的方式来解决。即定义一个快指针fast和一个慢指针slow,使得fast每次跳跃两个节点,slow每次跳跃一个节点...判断出链表有以后,则需要算出进入的第一个节点

    判断单向链表是否有环,可以采用快指针与慢指针两个指针的方式来解决。即定义一个快指针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 ...

    题目:如何判断一个单链表是否有环?若有环,如何找出环的入口节点。
    一、单链表是否有环
    思路分析:
    单链表有环,是指单链表中某个节点的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> 于是从链表头与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。

    展开全文
  • 判断链表有并返回入的第一个节点,c程序实现

    这个问题可以两部分组成:

    1、首席判读链表是否有环;

    2、有环的话,在公共点拆开:设在ptr1 == ptr2 ,那么ptr2前进一步:ptr2 = ptr2->next;ptr1拆链表:ptr1->next = NULL;

    此时,就有两个链表了:一个是原来的链表list1,在ptr1处结束;一个是以ptr1为头节点的新链表list2。于是问题转换成为了list1与list2的第一个公共节点。此问题已经解决。

    代码实现如下:

     

    展开全文
  • 返回入的第一个节点之前我们要判断是否成环,判断方法如下 判断了是否成环之后怎么找到成环的第一个节点呢,分析如下 代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ...

    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;
    }
    
    展开全文
  • 一个图可以有从起始节点到另一个节点的备用路径。 这提供了项目如何从一个节点流向另一个节点的视觉刺激。 Team Members 团队成员 社交资料 兴趣 戈德拉格茨纳恩 学号:u17132330 电子邮件:ntpnaane@gmail.com ...
  • 但如何返回入的第一个节点,当然最简单的思路是用额外的空间记录是否访问过该节点,如果访问过,就立刻停止遍历,并返回。在《程序员代码面试指南》中,作者采用了两个指针的方法,具体如下。 1设置一个slow指针...
  • 数据量较大,希望复杂度尽量低。 现在实现图的数据结构是用HashMap记录对应标号的节点,再分别对每个节点使用HashMap记录子节点。 感谢!
  • 这是LeetCode上面的142题,同时也是剑指offer上的一个题 整体思想:当判断完当前链表有之后,先确定的个数,确定完之后,让前面的指针开始先跑n个节点,然后两支针一起跑,两个指针相等的那个位置就是环形链表的...
  • 给定一个链表,返回链表开始入的第一个节点。 如果链表无,则返回 null。 为了表示给定链表中的,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有...
  • 博主面试的过程中遇到了这么一个面试题,判断一个链表是否带,并且如果有的话,要找到的入口节点,并且求出的长度~ 那么我们大家一起来分析一哈(っ•̀ω•́)っ✎⁾⁾ 假设链表的节点的结构是这样的 struct...
  • [转]给定单链表,检测是否有。如果有,则求出进入的第一个节点 转自:http://blog.csdn.net/dengsi23/article/details/7984291   判断单向链表是否有,可以采用快指针与慢指针的方式来解决。即定义一个
  • (1)给定一个链表,判断链表中是否有: 我们可以用快慢指针的方法解决这个问题。fast指针一次走2步,slow指针一次走1步,则当两个指针走一次时两个指针相差1步,走两次时相差2步,以此类推当走n次时fast指针与...
  • 分析:可以使用一个map来记录每个遍历过的节点,当遍历到一个之前遍历过的节点时(第一次出现这种情况),则说明链表存在了且这个节点的第一个节点,实现如下: /** * Definition for singly-linked list. *...
  • 我们用两个指针pslow和pfast从头开始遍历链表,pslow每次前进一个节点,pfast每次前进两个结点,若存在,则pslow和pfast肯定会在环中相遇,若不存在,则pslow和pfast能正常到达最后一个节点(实际上是到达NULL)。...
  • 如果离链表有的话,有节点肯定是共同的节点,通过标志位找节点或者通过链长度n以及循环的第n+1个节点肯定是第一个节点,然后用这个节点在第二个链中去遍历。  剑指offer上的193页,面试题37 ...
  • 淘宝的技术笔试题量不大,但是时间也很短(一个小时...题目:①判断一个单向链表是否有,如果有则找到的入口节点。  ②判断两个单向链表是否相交,如果相交则找到交点节点。 算法思想:①用两个指针p
  • 定义两个指针fast 和slow,fast每次向后移动两个节点,slow每次想后移动一个节点。 1.如果没有,则fast首先到达链表结尾; 2.链表有的情况下:fast与slow两次相遇,slow中间走过的节点处即为的长度; 3.找...
  • 双向链表删除一个节点P template void list::delnode(int p){ int k=1; listnode *ptr,*t; ptr=first; while(ptr->next!=NULL&&k!=p) { ptr=ptr->next; k++; }
  • 题目描述:单链表可能有... 的第一个节点;如果不相交,返回 null 即可。 首先,感谢程云老师的分享!以下是本问题的解决方法整理。 思路:  链表分有链表和无环链表,如果两个链表存在相交,则只有两种可能,两
  • 建立节点的有限元模型开展非线性承载力分析,考察采用6种不同节点板宽厚比钢管节点的荷载变形关系及其极限承载力。分析结果表明6种节点均具有良好的承载力特性和延性,节点板宽度增加有利于提高高强钢管...
  • 给定一个单链表,只给出头指针head: 1、如何判断是否存在? 2、如何知道的长度? 3、如何找出的连接点在哪里? 4、带链表的长度是多少?   解法: 1、对于问题1,使用追赶的方法,设定两个指针slow、...
  • 已有研究大多是通过传感器的坐标或者依据大量节点信息进行检测, 现提出算法通过检测每个节点的邻居节点是否能形成包围检测节点的闭合来判别当前节点是否为边界节点。该算法使得节点能够仅基于小邻域的信息自主地...
  • 这类问题通常使用双指针的方法,即一个快指针一个慢指针。faster = faster.next.next;slower = slower.next;“公理”:两指针相遇时,快指针走过的路程为慢指针的2倍。链表有时,有以下3中情况,右边和下边都是第...
  • 两个指向头节点的指针,fast和slow,一起从头结点开始往后遍历,fast每次移动两个节点,slow每次移动一个节点, 这样,如果存在结构,那么fast指针在不断绕过程中,肯定会追上slow指针。 # -*- coding:utf-8 -*...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 152,825
精华内容 61,130
关键字:

一个节点是环吗