【100题】第七题（单链表相交）

题目：给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交，为了简化问题，我们假设俩个链表均不带环。

问题扩展：
1，如果链表可能有环列?
2，如果需要求出俩个链表相交的第一个节点列?

解答：

一，关于链表有环的思考

理解： 1，如何判断链表有环？

思考：单链表有环的判断？什么意思？一直向后递归递归到p->next=NULL;不就完了？

更正：如果一直向后递归，假如存在环的话，会出现死循环。

方法：【一】：可以做标记的话，在第一个节点做上标记。若访问到标记节点则有环，若访问到NULL则无环。（这种方法不可取，只在所有节点构成一个整环时才可以）

下图：

【二】：不可以做标记的话，设置两个节点slow,fast。slow每次走一步，fast每次走两步。如果slow指针跟fast指针重合则表示有环。

【三】：应该还有方法待思考……

2，如何判断环的长度？

记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。

3，如何找到环的入口在哪里？

有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。(证明在后面附注)

4，带环链表的长度是多少？

问题2求出环的长度，问题3求出头指针到连接点的距离。两者相加等于链表长度。

程序源码：（待续）

void Isloop(Llink head)  //判断是否存在环，如果有环则输出（非环节点数，环节点数，总节点数）环开始节点
{
 if(!head||!head->next)
   return;
 Llink p,q;
 bool loop=false;
 p=q=head->next;
 while(q&&q->next)//判断是否有环
 {
  p=p->next;
  q=q->next->next;
  if(p==q)
  {
   loop=true;
   break;
  }
 }
 if(!loop)
  cout<<"This link has not loop\n";
 else
 {
  cout<<"This link has a loop\n";
  Llink r=p;
  q=head->next;
  int nonloop=1,loopcount=1;
  //nonloop计算非环结点数，loopcount计算环上结点数
  do//计算环上的结点数
  {
   p=p->next;
   ++loopcount;
  }while(p!=r);
  --loopcount;
  while(p!=q)//得到环的入口结点，同时计算得到非环的结点数
  {
   p=p->next;
   q=q->next;
   ++nonloop;
  }
  --nonloop;
  cout<<"\nStart of loop: "<<p->data<<endl;  //环开始的地方 
  cout<<"\nCount of nonloop: "<<nonloop //非环的结点数
      <<"\nCount of loop: "<<loopcount//环的节点数 
      <<"\nCount of Linknode: "<<nonloop+loopcount<<endl;//总共的节点数 
 }
}

寻找环的入口的源码：

slist* FindLoopPort(slist *head)  //单纯的找环开始点 
{  
    slist *slow = head, *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;  
    slow = head;  
    while (slow != fast)  
    {  
         slow = slow->next;  
         fast = fast->next;  
    }  
    return slow;  
} 

寻找环入口方法二：亦可以用类似与hash表的方法，即设立一个数组，将链表结点中的值做数组下标，当赋值冲突时就是环的接入点

bool isloop(Llink p)
{
 if(!p||!p->next)
  return true;
 int a[MAXSIZE],n=0;
 memset(a,0,sizeof(int)*MAXSIZE);
 p=p->next;
 while(p)
 {
  if(a[p->data]==-1)//存在环时，会发生冲突
  {
   cout<<"\nLoop node: "<<p->data<<endl
    <<"\nLen of node: "<<n<<endl;
   return true;
  }
  a[p->data]=-1;
  ++n;
  p=p->next;
 }
 return false;
}

创建一个有环的链表

Llink CreatlinkLoop()
//创建一个有环的链表
{
   Llink head=new Lnode;
   //head->data=0;
   head->next=NULL;
   Lelemtype e;
   Llink q=head;
   int N=0;
   cout<<"input elems:";
   while(cin>>e)
   {
      Llink p=new Lnode;
      ++N;
      p->data=e;
      p->next=q->next;
      q->next=p;
      q=p;
   }
   cin.clear();
   cin.sync();
   srand(time(0));
   q->next=Findnode(head,rand()%N);//随机产生环的接入点
   return head;
}
Llink Findnode(Llink head,int n)//找出链表中的第n个结点
{
   if(n<=0)
    return head;
   Llink p=head->next;
   for(int i=1;p&&i<n;++i)
       p=p->next;
   return p;
}

二，分析与解法

A----B----C------D、

、

I-----J----NULL

/

E-----F-----G------H

这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相交的情况,而且释放了其中一个链表的所有节点,那样就会造成信息的丢失,并且另一个与之相交的链表也会受到影响,这是我们不希望看到的。在特殊的情况下,的确需要出现相交的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
【解法一】直观的想法
看到这个问题,我们的第一个想法估计都是,“不管三七二十一”,先判断第一个链表的每个节点是否在第二个链表中。这种方法的时间复杂度为 O(Length(h1) * Length(h2))。可见,这种方法很耗时间。

【解法二】利用计数的方法（hash表 最简单）
很容易想到,如果两个链表相交,那么这两个链表就会有共同的节点。而节点地址又是节点的唯一标识。所以,如果我们能够判断两个链表中是否存在地址一致的节点,就可以知道这两个链表是否相交。一个简单的做法是对第一个链表的节点地址进行 hash 排序,建立hash 表,然后针对第二个链表的每个节点的地址查询 hash 表,如果它在 hash 表中出现,那么说明第二个链表和第一个链表有共同的节点。这个方法的时间复杂度为 O(max(Length(h1)
+ Length(h2)))。但是它同时需要附加 O(Length(h1))的存储空间,以存储哈希表。虽然这样做减少了时间复杂度,但是是以增加存储空间为代价的。是否还有更好的方法呢,既能够以线性时间复杂度解决问题,又能减少存储空间?

【解法三】链接“头尾”判断环法
由于两个链表都没有环,我们可以把第二个链表接在第一个链表后面,如果得到的链表有环,则说明这两个链表相交。否则,这两个链表不相交这样我们就把问题转化为判断一个链表是否有环。链表有环的情况判断一个链表是否有环,也不是一个简单的问题,但是需要注意的是,在这里如果有环,则第二个链表的表头一定在环上,我们只需要从第二个链表开始遍历,看是否会回到起始点就可以判断出来。最后,当然可别忘了恢复原来的状态,去掉从第一个链表到第二个链表表头的指向。这个方法总的时间复杂度也是线性的,但只需要常数的空间。
【解法四】最后结点地址比较法
仔细观察题目中的图示,如果两个没有环的链表相交于某一节点的话,那么在这个节点之后的所有节点都是两个链表所共有的。那么我们能否利用这个特点简化我们的解法呢?困难在于我们并不知道哪个节点必定是两个链表共有的节点(如果它们相交的话)。进一步考虑“如果两个没有环的链表相交于某一节点的话,那么在这个节点之后的所有节点都是两个链表共有的”这个特点,我们可以知道,如果它们相交,则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点,所以这成了我们简化解法的一个主要突破口。

先遍历第一个链表,记住最后一个节点。然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则,不相交。这样我们就得到了一个时间复杂度,它为 O((Length(h1) + Length(h2)),而且只用了一个额外的指针来存储最后一个节点。这个方法比解法三更胜一筹。

【如果两个有环】判断第一个链，直链跟环交点为O1,判断第二个链，直链跟环交点为O2。

比较O1跟O2地址，如果相等则相交，否则从O1遍历，每次与O2地址比较，直到回到O1。期间有相等的则相交，否则不想交。