精华内容
下载资源
问答
  • 检测单向链表是否存在 正文: 问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个,...

    原文链接:

    检测单向链表是否存在环

    正文:

    问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个环,在顺序遍历链表的时候,程序就会陷入死循环。我们的问题就是,如何检测一个链表中是否有环,如果检测到环,如何确定环的入口点(即求出环长,环前面的链长)。

    一种比较耗空间的做法是,从头开始遍历链表,把每次访问到的结点(或其地址)存入一个集合(hashset)或字典(dictionary),如果发现某个结点已经被访问过了,就表示这个链表存在环,并且这个结点就是环的入口点。这需要O(N)空间和O(N)时间,其中N是链表中结点的数目。

    如果要求只是用O(1)空间、O(N)时间,应该怎么处理呢?

    其实很简单,想象一下在跑道上跑步:两个速度不同的人在操场跑道上一圈一圈地跑,他们总会有相遇的时候。因此我们只需要准备两个指针,同时从链表头出发,一个每次往前走一步,另一个每次往前走两步。如果链表没有环,那么经过一段时间,第二个(速度较快的)指针就会到达终点;但如果链表中有环,两个指针就会在环里转圈,并会在某个时刻相遇。

    大家也许会问,这两个指针要在环里转多少圈才能相遇呢?会不会转几千几万圈都无法相遇?实际上,第一个(速度慢的)指针在环里转满一圈之前,两个指针必然相遇。不妨设环长为L,第一个指针P1第一次进入环时,第二个指针P2在P1前方第a个结点处(0< a < L),设经过x次移动后两个指针相遇,那么应该有0 + x = a + 2x (modL),显然x = L - a。下面这张图可以清晰地表明这种关系,经过x =L - a次移动,P1向前移动了L - a个位置(相当于后退了a),到达P1′处,而P2向前移动了2L - 2a个位置(相当于后退了2a),到达P2′处,显然P1′和P2′是同一点。

    在知道链表内有环后,求环长是一件非常简单的事情,只要从刚才那个相遇点开始,固定P2,继续移动P1,直到P1与P2再次相遇,所经过的步数就是环长。

    怎么求环前面那段子链的长度呢?很简单,让P1和P2都回到链表起点,然后让P2先往前走L次(每次往前走一步),然后P1和P2再同时往前走,当它们再次相遇时,P1所走的步数就是环前面的子链长度。


    算法示意:

    def CheckRing(head):
      l1 = 0  # length of the chain before the ring
      l2 = 0  # length of the ring
    
      # Check if there is a ring.
      pos1 = head
      pos2 = head
      while pos2 and pos2.next:
        pos1 = pos1.next
        pos2 = pos2.next.next
        l1 += 2
        if pos2 and pos1 == pos2:
          l2 = 1
          break
      if not l2:
        if pos2: l1 += 1
        return (l1, l2)  # l2 should be 0
    
      # Calc the length of the ring.
      pos1 = pos2.next
      while pos1 != pos2:
        pos1 = pos1.next
        l2 += 1
    
      # Calc the length of the chain before the ring.
      l1 = 0
      pos1 = head
      pos2 = head
      for i in xrange(l2):
        pos2 = pos2.next
      while pos1 != pos2:
        pos1 = pos1.next
        pos2 = pos2.next
        l1 += 1
      return (l1, l2)



    展开全文
  • 有一个单向链表,链表当中有可能出现,就像下图这样。我们如何判断一个单向链表是否有呢? 那么第一步,我们先实现一个这样的链表,接着再说如何判断这样的链表。 实现有单向链表 1、定义add(Node node)...

    Java实现有环的单向链表,并判断单向链表是否有环

    有一个单向链表,链表当中有可能出现环,就像下图这样。我们如何判断一个单向链表是否有环呢?

    那么第一步,我们先实现一个这样的链表,接着再说如何判断这样的链表。

    实现有环的单向链表

    1、定义add(Node node)方法

        /**
         * 向链表末尾添加结点
         *
         * @param node 结点的next指向为null,表示尾结点。
         * @return
         */
        public boolean add(SingleNode node) {
            if (first == null) {
                first = node;
            } else {
                SingleNode last = get(getSize() - 1);
                last.next = node;
            }
            size++;
            return true;
        }
    
        /**
         * 末尾添加一个特殊结点,形成一个环,为了测试用。
         *
         * @param node 这个node的next指向单项链表中已经存在的结点。
         * @return
         */
        public boolean addCycleNode(SingleNode node) {
            if (getSize() < 2) {
                return false;
            }
            SingleNode last = get(getSize() - 1);
            last.next = node;
            return true;
        }
    

    2、先正常生成一个无环的单向链表,最后在末尾添加一个结点,让该结点的next指向前面的某个结点。

            // 循环链表
            SingleLinkedList sll = new SingleLinkedList();
            SingleNode head = new SingleNode(0, null);
            sll.add(head);
            for (int i = 1; i < 10; i++) {
                SingleNode node = new SingleNode(i, null);
                sll.add(node);
            }
            SingleNode sn = new SingleNode(111, null);
            sll.add(sn);
            for (int i = 10; i < 20; i++) {
                SingleNode node = new SingleNode(i, null);
                sll.add(node);
            }
            System.out.println(sll.toString());
    

    输出如下:此时打印的还是一个无环单向链表。

    SingleLinkedList:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 111, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    

    接着添加最后一个结点,让其next指向之前的sn结点,这样就形成了一个闭环。

            // 最后一个结点的next指向之前添加的某个结点。
            SingleNode last = new SingleNode(222, sn);
            sll.add(last);
    
    

    接着打印结果:需要注意的是,这里的打印log的方法我做了处理,具体细节请查看源码。

    cycle:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 111, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 222, 111]
    

    最后插入的结点的值为222,它的next指向的是111结点,如上所示,在222之后打印的就是111节点了,如果继续打印,就会一直循环打印下去。

    判断单向链表是否有环

    方法一:使用Hash Table
    判断一个链表是否有环,我们只需要判断某个结点是否之前被访问过即可。这里我们优先想到的就是使用Hash表进行存储。
    我们依次遍历访问每个结点,并将结点的引用存储到hash表中。如果当前结点是null,说明我们到达链表未尾部了,则当前链表一定无环;如果当前结点在hash表中已经存储过了,此时返回true即可。代码如下:

        /**
         * 判断单链表中是否有环
         * 借助HashSet来判断。
         *
         * @param head
         * @return
         */
        public boolean hasCycleByHashSet(SingleNode head) {
            Set<SingleNode> set = new HashSet<>();
            SingleNode node = head;
            while (node != null) {
                if (set.contains(node)) {
                    return true;
                } else {
                    set.add(node);
                }
                node = node.next;
            }
            return false;
        }
    

    方法二:使用快慢指针
    首先创建两个指针1和2(在Java里就是两个对象引用),同时指向这个链表的头结点。然后开始一个大循环,在循环体中,1每次移动一个结点,2每次移动2个结点。最后比较这两个结点指向的结点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

    代码如下:

        /**
         * 判断单链表中是否有环
         * 借助快慢指针来判断。
         *
         * @param head
         * @return
         */
        public boolean hasCycleByTowPointers(SingleNode head) {
            // 排除无数据或者只有一个数据且无闭环的情况
            if (head == null || head.next == null){
                return false;
            }
            SingleNode slow =  head;
            SingleNode fast = head.next;
            while(slow != fast){
                // 判断快指针结点是否为null,如果为null,则说明到达单向链表的结尾了。
                if(fast == null || fast.next == null){
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    

    完整代码请查看

    项目中搜索SingleLinkedList即可。
    github传送门 https://github.com/tinyvampirepudge/DataStructureDemo

    gitee传送门 https://gitee.com/tinytongtong/DataStructureDemo

    参考:
    1、linked-list-cycle

    2、漫画算法:如何判断链表有环?

    3、使用Java实现单向链表,并完成链表反转。

    展开全文
  • 题目为:对于普通的单向链表,如果实现确定其内部有一个,如何确定何处出现环路的?单向链表每个节点中只有data和next两个字段。  (单向链表含环路,不要总是想到“0”型环路,还要想到“6”字型环路)  原本...

    题目为:对于普通的单向链表,如果实现确定其内部有一个环,如何确定何处出现环路的?单向链表每个节点中只有data和next两个字段。

          (单向链表含环路,不要总是想到“0”型环路,还要想到“6”字型环路)

          原本听到这道题时,我首先想到的笨办法就是:建一个足够大的一维数组,,每个位置放Node*类型指针。而后开始遍历单向链表,遍历过一个节点后就将该节点的指针添加到这个一维数组中,随后与该数组前边的所有元素进行一次遍历比较,如果有重复,则定位到了这个出现环路的节点。

          但是后来面试官说:这个空间复杂度有点大,如果场景是有几百万条记录呢?有没有办法大大的降低这个时间复杂度?    因为是电面的,自己一时也没想出什么好办法来,惭愧惭愧~今天一早请教了下龙哥,龙哥给出了一个不错的思路,我测了一下,没有问题。

          主体思路是:

          从头结点开始遍历整个链表,没遍历过一个节点:就将其next置为NULL.这样:当往后遍历到某个节点:其next指向节点的next为NULL时变找到了。 注意:①很多人看到后会说:你这样不是破坏了原先的单向链表了吗?的确是这样,所以在考虑这种算法时还要同时考虑该如何进行恢复!最好是:使用完了之后接着恢复。而要做到这一点只能用递归来实现。(不过用递归貌似还是很大空间复杂度)

    1. struct Node     
    2. {     
    3.     int data;     
    4.     int pNext;     
    5. };     
    6.     
    7. void Fun(Node* pData,int currentPos,int& callbackPos)     
    8. {     
    9.     if(pData[currentPos].pNext)     
    10.     {     
    11.         int backup = pData[currentPos].pNext;     //记录下后继节点  
    12.         pData[currentPos].pNext = NULL;     
    13.         Fun(pData,backup,callbackPos);     
    14.         pData[currentPos].pNext = backup;     //恢复后继节点  
    15.     }     
    16.     else    
    17.     {     
    18.         callbackPos = currentPos;     
    19.     }     
    20. }     
    21. int main()     
    22. {     
    23.     //initilze array:     
    24.     Node* pData = new Node[7];     
    25.     for(int i=0;i<6;i++)     
    26.     {     
    27.         pData[i].pNext = i+1;     
    28.     }     
    29.     pData[6].pNext = 3;     
    30.     
    31.     for(int i=0;i<7;i++)     
    32.     {     
    33.         pData[i].data = 10;     
    34.     }     
    35.     //-----------------------     
    36.     int callback = -1;     
    37.     Fun(pData,0,callback);     
    38.     printf("%d/n", callback);     
    39.     system("pause");     
    40.          return 0;     
    41. }    
        

        所以:有时候递归用来处理这种既需要全局变化,又需要恢复的算法时很有用。


    本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/NRC_DouNingBo/archive/2010/06/23/5688868.aspx

     

    还有另外一篇介绍的方法,比这个方法要简答

    有一个单向链表,如何判定这个链表当中是否包含有环路,以及如何定位环路在链表当中的开始点呢?

    关于第一个问题,网络上可以搜索到,用两个指针来遍历这个单向链表,第一个指针p1,每次走一步;第二个指针p2,每次走两步;  当p2 指针追上 p1的时候,就表明链表当中有环路了。

    关于这个解法最形象的比喻就是在操场当中跑步,速度快的会把速度慢的扣圈

    可以证明,p2追赶上p1的时候,p1一定还没有走完一遍环路,p2也不会跨越p1多圈才追上

    我们可以从p2和p1的位置差距来证明,p2一定会赶上p1但是不会跳过p1的

    因为p2每次走2步,而p1走一步,所以他们之间的差距是一步一步的缩小,4,3,2,1,0 到0的时候就重合了

    根据这个方式,可以证明,p2每次走三步以上,并不总能加快检测的速度,反而有可能判别不出有环

    比如,在环的周长L是偶数的时候,初始p2和p1相差奇数的时候,p2每次走三步,就永远和p1不重合,因为他们之间的差距是:  5, 3 , 1,  L-1, L-3


    关于第二个问题,如何找到环路的入口,是这里要重点说明的内容:

    解法如下: 当p2按照每次2步,p1每次一步的方式走,发现p2和p1重合,确定了单向链表有环路了

    接下来,让p2回到链表的头部,重新走,每次步长不是走2了,而是走1,那么当p1和p2再次相遇的时候,就是环路的入口了。

    这点可以证明的:

    在p2和p1第一次相遇的时候,假定p1走了n步骤,环路的入口是在p步的时候经过的,那么有

    p1走的路径: p+c = n;         c为p1和p2相交点,距离环路入口的距离

    p2走的路径: p+c+k*L = 2*N;   L为环路的周长,k是整数

    显然,如果从p+c点开始,p1再走n步骤的话,还可以回到p+c这个点

    同时p2从头开始走的话,经过n不,也会达到p+c这点

    显然在这个步骤当中p1和p2只有前p步骤走的路径不同,所以当p1和p2再次重合的时候,必然是在链表的环路入口点上

    1. #include "iostream.h"  
    2. #include "memory.h"  
    3. #include "new.h"  
    4. class CList {  
    5. public:  
    6.  int nData;  
    7.  CList * pNext;  
    8. } * pRoot = NULL;  
    9.   
    10. const int size = sizeof(CList) / sizeof(int);  
    11. int  buffer[101*size];  
    12. bool Init(int n)  
    13. {  
    14.     pRoot = (CList*)buffer;  
    15.  if ( n<1 && n>98 )  return false;  
    16.  CList * pTemp = NULL;  
    17.  for ( int i=0; i<101; i++ ) {  
    18.     pTemp = new (buffer+i*size) CList();  
    19.     pTemp->nData = i;  
    20.     pTemp->pNext = (CList *)(buffer + (i+1)*size);  
    21.  };  
    22.  pTemp->pNext = (CList *) (buffer + n*size);  
    23.  return true;  
    24. }  
    25.   
    26. void ClearCircle(CList * pRoot)  
    27. {  
    28.  CList * p1, * p2;  
    29.  p1 = p2 = pRoot;  
    30.  do {  
    31.      p2 = p2->pNext->pNext;  
    32.   p1 = p1->pNext;  
    33.  } while ( p2!=NULL && p1!=p2); //这里有问题吧,如果p2->pNext为NULL,p2->pNext->pNext就指向未知位置了,有危险,所以应该加上 p2->pNext!=NULL判断条件
    34.  if ( p1 == p2 ) {  
    35.   p2 = pRoot;  
    36.   while (1) {  
    37.    p2 = p2->pNext;  
    38.    if ( p1->pNext == p2 ) break;  
    39.    p1 = p1->pNext;  
    40.   }   
    41.   p1->pNext = NULL;  
    42.  }  
    43. }  
    44.   
    45. main()  
    46. {  
    47.     CList * pList = pRoot;  
    48.  if (Init(21) )   
    49.  {  
    50.   cout << "Before clear:!" << "/r/n";  
    51.   pList = pRoot;  
    52.   for ( int i=0; i<104; i++)  
    53.   {  
    54.    cout << pList->nData << "/r/n";  
    55.    pList = pList->pNext;  
    56.   }  
    57.   ClearCircle(pRoot);  
    58.  }  
    59.  cout << "After clear:" << "/r/n";  
    60.  pList = pRoot;  
    61.  while (pList) {  
    62.   cout << pList->nData << "/r/n";  
    63.   pList = pList->pNext;  
    64.  }  
    65.  return 0;  
    66. }  


    本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/happy__888/archive/2005/12/21/558356.aspx

    转自:http://blog.csdn.net/seanyxie/article/details/5825261

    展开全文
  • 小编想问大家一个问题,就是如果我们需要进行测试一个单向链表是否存在,应该使用什么方法才是最好的呢?如果大家还不知道有什么方法的话,那就接着往下面看哟!因为今天小编就要为大家介绍一下:在C语言中单向...

    小编想问大家一个问题,就是如果我们需要进行测试一个单向链表是否存在环,应该使用什么方法才是最好的呢?如果大家还不知道有什么方法的话,那就接着往下面看哟!因为今天小编就要为大家介绍一下:在C语言中单向链表环测试并返回环起始节点的实现方法。

    原始方法:

    就刚刚小编所提出的问题,也许会有朋友想到了一个非常原始的方法,那就是将链表的数据结构进行改变,然后给每一个节点添加一个名为bool的变量,在还没有进行测试的时候,我们全部都初始化成为false值,接着遍历链表,每当我们访问到一个节点的时候,首先要做的就是测试其bool成员来确定这个节点是否已经被我们访问过了。假如说我们所测试出来的值是为true的话,那么就代表着访问过,就是有环的意思。否则的话,就设置bool成员为true的值,表示访问过的意思,接下来我们还要继续进行测试。

    假如我们在不改变数据结构的情况下,我们还有以下一种的解决方案。具体是哪种解决方案呢?请大家留意下面的教程:

    第一步:测试是否有环

    第一种解决的方案就是先测试一下是否有环。首先我们可以先构建出两个迭代器来进行遍历链表,有一个迭代器每一次移动一个节点,另外一个迭代器则每一次移动两个节点。假如说这两个一快一慢的土鳖迭代器相遇了的话,那就可以证明一件事情,那就是他们两个迭代器在某一个时刻都已经到了同一个节点。这样子的话,我们可以非常的肯定的确是有环存在的。其实最直观的理解就是把这两个土鳖迭代器一快一慢的在长度400米环形跑道上各自选择一个位置,接着同一时间顺时针做死了跑,那么这样子的话,这两个土鳖迭代器总可以相遇的。那么有人就会问小编,到底是为什么呢?原因就是因为有一个迭代器会比另外一个迭代器速度要快。

    假如有一些朋友是需要进行严谨证明的话,那么我们还可以这样来理解。具体的理解如下:首先我们想象着在某一个迭代的时刻,这两个土鳖迭代器(在接下来的教程中,小编会将其简单称为土鳖,因为这样会更有亲切感,哈哈)都进入了环,一个土鳖距离环的起始点为i,然而另外一个土鳖距离环起始点为j。这个想象是一定有成立的时刻,因为在跑着跑着的时候,这两个土鳖总会进入环,而且一旦进入了环那就再也出不来了,只可以做死了跑。

    接下来我们再大胆的进行假设一下这两个土鳖又相互跑了一会儿,他们居然相遇了,有一个土鳖跑了x步,另外一个土鳖则跑了2x步。假如说这个环一共是长n米的话,换句话来说,也就是速度慢的土鳖需要跑n步才可以跑完一圈。接下来我们就可以得出i+x以及j+2x对于n同余,就说明了一件事,那就是:i+x以及j+2x除以n的余数是一模一样的,可以写成同余等式就是(i+x)=j+2x(modn)。然后我们就可以根据同余加减法性质,让上面的表达式来减去x=x(modm),就可以得到以下的表达式:i=(j+x)(modm)。在这个表达式中,大家可以看到因为x是一个未知数,因此在上面的表达式是一个同余方程,另外的字母i、j通通都是普通整数,非常明显其实这个方程是有解的。就比如说:表达式2=(1+x)(mod5)的一个简单解就是数字1。因此这两个土鳖跑着跑着就一定会相遇的。换句话来说,就是我们上面所检测环的算法是可行的方法,不会发生死循环的情况。

    第二步:获取环起始点

    好了,基于问题一的分析,我们就可以知道了一件事,那就是速度快的土鳖以及速度慢的土鳖一定会在某一个节点进行相遇的。现在我们就把这个点(相遇的节点)假设成为cross,同一时间我们也将环起始点假设成为start。在这里,有一个十分显然的事实,那就是当两个土鳖相遇的时候,速度慢的土鳖所跑过的路径是速度快土鳖的一半。这样子的话,他们两个在相遇之前,当速度慢土鳖跑了一半时,速度快土鳖就已经经过了相遇点(跨越又或者是落脚)。这样子的话,当速度慢土鳖跑完后半段时,速度快土鳖就已经从相遇的地方开始又跑了一模一样的路程到达了相遇的地点。这个路程的长度就是相等于速度慢土鳖一共跑的长度。

    那么现在最神奇的地方要来了,那就是假如说速度慢土鳖从头开始跑时,有另外一个速度慢土鳖从相遇的地方cross开始跑,那么这两个土鳖也一定会在相遇的地方进行相遇,接着我们就将这两个土鳖称为分别为A以及B。当B土鳖走的路程以及速度快土鳖后半段时间走过的路程是完全一模一样的,唯一一个的区别就是他稍微慢了一点而已。

    那么现在第二个最神奇的地方又要来了,大家都已经知道速度慢土鳖A以及B土鳖的速度是一模一样的,那么这两个土鳖在相遇地点之前的节奏也是一模一样的,换句话来说,就是他们在相遇地点之前就已经开始相遇了,而且还是以完全一样的速度相伴走到了相遇的地方cross。那么这两个土鳖究竟是从什么时候相遇开始这一段快乐旅程的呢?有人知道答案吗》没错,就是从环起始点start开始相遇的。在这里,我们可以让速度慢土鳖A以及B土鳖从相遇地方倒退,这样我们就可以理解到为什么他们会在start点进行相遇了。

    好了,现在我们就已经有了解决方案了,具体的解决方案如下:先让速度慢土鳖A从链表头start开始跑,让另外一个速度慢土鳖从相遇点cross开始跑。有人知道这两个土鳖第一次相遇的地方是哪里吗?正确答案就是——环起始点。

    最后,为了可以更加方便大家深入的理解,小编在这里特意给大家带来了C++的代码。具体编程代码,如下图:

    5403007f8477b58b4508cff23314bb84.png

    c0a580a590071af4861662eb325330bb.png

    7b729ac3aeb2250b200f57dc024dee2f.png

    d89804acd3b2113bed9e6fddf9e837d4.png

    小编结语:

    在这篇教程中,小编主要是向大家介绍一下在C语言中单向链表环测试并返回环起始节点的实现方法。教程的确是有一点点长,但是总的来说,还是比较详细的,所以大家一定要有点耐心的去看哟!不要半途而废了。

    课课家会一直更新编程语言的教程,请继续关注我们的网站:课课家教育。谢谢!

    展开全文
  • 判断单链表是否有问题汇总判断是否有思路代码找出的入口点思路代码求的长度思路代码求上距离任意一点最远的点判断两个无环链表是否相交判断相交的位置 问题汇总 ...如何判断两个无环链表...
  • 环单向链表

    千次阅读 2015-09-26 19:03:52
     判断单向链表是否有,可以采用快指针与慢指针的方式来解决。即定义一个快指针fast和一个慢指针slow,使得fast每次跳跃两个节点,slow每次跳跃一个节点。如果链表没有的话,则slow与fast永远不会相遇(这里链表...
  • 1.若链表没有,则在q等于null之前,p永远追不上q,即q到链表尾部时即可确定该链表没有; 2.若链表,则q会回到p的左边,当q最接近p时,有下面两种情况: (1)p和q再向右走一步,则会相遇 (2)p和q再向右走两步...
  • 有时候我们需要测试一个单向链表是否存在。最土鳖的方法就是改变链表的数据结构,给每个节点添加一个bool变量,在未测试时全部初始化为false,然后遍历链表,每访问一个节点,先测试其bool成员来确定这个节点是否...
  • 单向链表上是否有

    2014-11-13 15:08:50
    有一个单链表,其中可能有一个,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一。问题:1、如何判断一个链表是不是这类链表?2、如果链表为存在,如果找到的入口点?解答: 1...
  • 单链表的反转、检测、两个有序链表的合并、判断单向链表是否是回文字符串
  • 问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个,在顺序遍历链表的时候,程序就会陷入...
  • 首先遍历链表,寻找是否有相同地址,借此判断链表中是否有 方法一 如果不考虑空间复杂度,可以使用一个map记录走过的节点,当遇到第一个在map中存在的节点时,就说明回到了出发点,即链表,同时也找到了的...
  • 定义两个指针,同时从链表的头结点出发,一个指针一次走一步,另外一个指针一...代码如下:我写了两个测试用例,一个带的,一个不带的,带如果添加Destroy语句,程序运行会出现下面的错误: 打断点发现destr
  • 判断一个单向链表中是否有

    千次阅读 2015-11-23 23:04:13
    题目分析这是一道经典的面试题,据说还是从微软传出来的,我们来看看这个问题的通用解法...即当(pSlow == pFast)时就表示有,若pFast快指针先到了结尾则表示无,实现的代码如下:struct listtype { int data; l
  • //////题目:两个单向链表,找出它们的第一个公共结点。 ////// //////链表的结点定义为: ////// //////struct ListNode ////// //////{ ////// ////// int m_nKey; ////// ////// ListNode* m_pNext; ////// /////...
  • 判断单向链表中是否有C++实现

    千次阅读 2019-04-17 15:50:30
    判断链表是否有的经典的方法是快慢指针的方法。 快指针pf每次移动两个节点,慢指针ps每次移动一个节点,如果指针可以追上慢指针,那就说明其中有一个,反之没有。 结论:链表存在,则fast和slow两指针...
  • 1.如果在单向链表中有如何检测? 2.如何知道的长度? 3.如何知道外长度,或者说是由链表头结点到碰撞点的长度? 4.如何知道整条链的长度? 5.如果存在又该如何消除? 问题1:如何检测单向链表的...
  • C语言单向链表环测试并返回起始节点的方法有时候我们需要测试一个单向链表是否存在。最土鳖的方法就是改变链表的数据结构,给每个节点添加一个bool变量,在未测试时全部初始化为false,然后遍历链表,每访问一个...
  • 如何检查一个单向链表上是否有?

    千次阅读 2013-11-20 16:29:40
    有一个单链表,其中可能有一个,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一。 问题: 1、如何判断一个链表是不是这类链表? 2、如果链表为存在,如果找到的入口点?...
  • 单向链表相关

    2012-04-10 16:42:41
    单向链表是微软笔试常考的,参考这里:http://www.cnblogs.com/tdyizhen1314/archive/2012/04/03/2431124.html   #include&lt;iostream&gt; using namespace std; struct node{ int data; struct...
  • # @File : 拓展单向链表.py # @Date : 2019/3/26 0026 # @Contact : 1329778364@qq.com # @Author: DeepMan """ 这一节主要介绍链表的其他操作 包括交叉 环形判断。等 """ class Node: de...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,040
精华内容 1,216
关键字:

单向链表检测环