IT公司100题-7-判断两个链表是否相交

问题：
有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。
1、如何判断一个链表是不是这类链表？

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

分析：

在无环的情况下，如果两个链表有结点相同，那么它们下一结点也相同，如此可推出尾结点也相同。

那么只要判断两链表的尾结点是否相同。（O(len1+len2)）

 1 struct Node {
 2   int data;
 3   int Node *next;
 4 };
 5 // if there is no cycle.
 6 int isJoinedSimple(Node * h1, Node * h2) {
 7     while (h1->next != NULL)
 8         h1 = h1->next;
 9     while (h2->next != NULL)
10         h2 = h2-> next;
11     return h1 == h2;
12 }

扩展1：

需要先判断有环无环，可以这样做，定义两个指针，指向头结点，一个每次移动一个结点，另一个每次移动两个结点，如果慢的能追上快的（也就是两个指针重逢），就说明有环。

 1 // 7.cc
 2 bool has_loop(link_list* link) {
 3     link_list* fast = link;
 4     link_list* slow = link;
 5 
 6     while (fast != NULL && fast->next != NULL) {
 7         fast = fast->next->next;
 8         slow = slow->next;
 9         if (fast == slow)
10             return true;
11     }
12     return false;
13 }

利用如下方法分别找到两个链表的环入口。首先设置一个快慢指针p_fast和p_slow，找到两个指针相交的点，p_inter。然后p从链表开头，p_slow从p_inter开始走，每次都走1步，则两个指针相交的地方，就是链表的入口。

(a) 分别求得A和B两个链表的入口，如果一样。则两个链表相交的第一个节点方法同1，只是将环当成NULL即可。

(b) 如果两个链表的环入口不一样，则没有第一个相交节点。

扩展2：

如何找到入口点：

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr
s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：

 1 slist* FindLoopPort(slist *head)
 2 {
 3     slist *slow = head, *fast = head;
 4 
 5     while ( fast && fast->next ) 
 6     {
 7         slow = slow->next;
 8         fast = fast->next->next;
 9         if ( slow == fast ) break;
10     }
11 
12     if (fast == NULL || fast->next == NULL)
13         return NULL;
14 
15     slow = head;
16     while (slow != fast)
17     {
18          slow = slow->next;
19          fast = fast->next;
20     }
21 
22     return slow;
23 }