判断两个无环链表是否相交

题目：给定两个无环的单链表，判断两者是否相交（即有共同的节点）。

思路：可以将其中一个链表连接到另一个链表尾部，并通过判定得到新的链表是否有环来确定两个链表是否相交。

代码：

 1 #include <cstdio>
 2 
 3 typedef struct node
 4 {
 5     struct node* next;
 6 }Node, *pNode;
 7 
 8 int bListIntersect (Node list1, Node list2);
 9 
10 int main (int argc, char** argv)
11 {
12     Node n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;
13     n1.next = &n2;
14     n2.next = &n3;
15     n3.next = &n4;
16     n4.next = NULL;
17 
18     n5.next = &n6;
19     n6.next = &n7;
20     n7.next = NULL;
21 
22     n8.next = &n9;
23     n9.next = &n10;
24     n10.next = &n3;
25 
26     printf(bListIntersect(n1, n5) == 1?"intersect
":"not intersect
");
27     printf(bListIntersect(n1, n8) == 1?"intersect
":"not intersect
");
28 
29     return 0;
30 }
31 
32 int bListIntersect (Node list1, Node list2)
33 {
34     pNode p, q;
35     p = &list1;
36     while (p->next != NULL)
37     {
38         p = p->next;
39     }
40 
41     p->next = &list2;
42     q = p;
43     p = p->next;
44     while ((p != NULL) && (p != q))
45     {
46         p = p->next;
47     }
48     q->next = NULL;
49     return (p == NULL) ? 0 : 1;
50 }