检测两个链表是否有交点

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

思路：

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

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

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

代码：

[cpp][/cpp] view plaincopyprint?

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()函数请看“单链表基础”