面试题(循环链表)

晨曦之光 发布于 2012/04/13 11:20
阅读 190
收藏 1

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

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

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

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

      主体思路是:

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

struct Node   
{   
    int data;   
    int pNext;   
};   
  
void Fun(Node* pData,int currentPos,int& callbackPos)   
{   
    if(pData[currentPos].pNext)   
    {   
        int backup = pData[currentPos].pNext;     //记录下后继节点
        pData[currentPos].pNext = NULL;   
        Fun(pData,backup,callbackPos);   
        pData[currentPos].pNext = backup;     //恢复后继节点
    }   
    else  
    {   
        callbackPos = currentPos;   
    }   
}   
int main()   
{   
    //initilze array:   
    Node* pData = new Node[7];   
    for(int i=0;i<6;i++)   
    {   
        pData[i].pNext = i+1;   
    }   
    pData[6].pNext = 3;   
  
    for(int i=0;i<7;i++)   
    {   
        pData[i].data = 10;   
    }   
    //-----------------------   
    int callback = -1;   
    Fun(pData,0,callback);   
    printf("%d/n", callback);   
    system("pause");   
         return 0;   
}  
    

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


本文来自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再次重合的时候,必然是在链表的环路入口点上

#include "iostream.h"
#include "memory.h"
#include "new.h"
class CList {
public:
 int nData;
 CList * pNext;
} * pRoot = NULL;

const int size = sizeof(CList) / sizeof(int);
int  buffer[101*size];
bool Init(int n)
{
    pRoot = (CList*)buffer;
 if ( n<1 && n>98 )  return false;
 CList * pTemp = NULL;
 for ( int i=0; i<101; i++ ) {
    pTemp = new (buffer+i*size) CList();
    pTemp->nData = i;
    pTemp->pNext = (CList *)(buffer + (i+1)*size);
 };
 pTemp->pNext = (CList *) (buffer + n*size);
 return true;
}

void ClearCircle(CList * pRoot)
{
 CList * p1, * p2;
 p1 = p2 = pRoot;
 do {
     p2 = p2->pNext->pNext;
  p1 = p1->pNext;
 } while ( p2!=NULL && p1!=p2);
 if ( p1 == p2 ) {
  p2 = pRoot;
  while (1) {
   p2 = p2->pNext;
   if ( p1->pNext == p2 ) break;
   p1 = p1->pNext;
  } 
  p1->pNext = NULL;
 }
}

main()
{
    CList * pList = pRoot;
 if (Init(21) ) 
 {
  cout << "Before clear:!" << "/r/n";
  pList = pRoot;
  for ( int i=0; i<104; i++)
  {
   cout << pList->nData << "/r/n";
   pList = pList->pNext;
  }
  ClearCircle(pRoot);
 }
 cout << "After clear:" << "/r/n";
 pList = pRoot;
 while (pList) {
  cout << pList->nData << "/r/n";
  pList = pList->pNext;
 }
 return 0;
}


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


原文链接:http://blog.csdn.net/xie376450483/article/details/5825261
加载中
返回顶部
顶部