检测两个链表是否有交点

题目:给定两个单链表(first, second),检测两个链表是否有交点,如果有返回第一个交点。

思路:

如果first==second,那么显然相交,直接返回first。

否则,分别从first,second开始遍历两个链表获得其长度len1与len2。假设len1>len2,那么指针p1由first开始向后移动len1-len2步。

指针p2=second,下面p1、p2每次向后前进一步并比较是否相等,如果相等即返回该结点,否则说明两个链表没有交点。

代码:

 

[cpp][/cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片

  1. Node *IsIntersect(Node *first, Node *second)
  2. {
  3.     if(first == NULL || second == NULL)
  4.     {
  5.         return NULL;
  6.     }
  7.     Node *p1, *p2;
  8.     p1 = first;
  9.     p2 = second;
  10.     int len1 = Length_LinkList(first);
  11.     int len2 = Length_LinkList(second);
  12.     if(len1 >= len2)
  13.     {
  14.         for(int i = 0; i < len1-len2; i++)
  15.         {
  16.             p1 = p1->next;
  17.         }
  18.     }else
  19.     {
  20.         for(int i = 0; i < len2-len1; i++)
  21.         {
  22.             p2 = p2->next;
  23.         }
  24.     }
  25.     while(p1 != NULL && p2 != NULL)
  26.     {
  27.         if(p1 == p2)
  28.         {
  29.             return p1;
  30.         }
  31.         p1 = p1->next;
  32.         p2 = p2->next;
  33.     }
  34.     return NULL;
  35. }

注:代码中所用到的计算单链表长度的Length_LinkList()函数请看“单链表基础”

标签