链表：两链表相交的一系列问题

题目：

在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1 和 head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回 null 即可。

要求：如果链表1和2的长度分别为M、N，时间复杂度请达到O（M+N），额外空间复杂度达到O（1）

分析：

本题需要拆分成三个子问题进行讨论：

1. 如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null。

2. 如何判断两个无环链表是否相交，相交则返回第一个相交的节点，不相交则返回null。

3. 如何判断两个有环链表是否相交，相交返回第一个相交点，不相交返回null。

首先解决第一问题。这个问题是 leetcode 141、142，具体思路可看网上说明

 1 public Node getLoopNode(Node head)
 2 {
 3     if(head == null || head.next == null || head.next.next == null)
 4     {
 5         return null;
 6     }
 7     Node slow = head.next, fast = head.next.next;
 8     while(fast != slow)
 9     {
10         if(fast.next == null || fast.next.next == null)
11             return null;
12         slow = slow.next;
13         fast = fast.next.next;
14     }
15 
16     fast = head;
17     while(fast != slow)
18     {
19         fast = fast.next;
20         slow = slow.next
21     }
22     return slow;
23 }

解决了问题一后我们就知道了两个链表有环或无环的情况。如果一个链表有环，另一个无环，那么这两个链表无论如何也不可能相交。能相交的情况就两种，一种是两个链表都无环即问题二；另一个两个链表都有环，即问题三。

问题二的解法：

1. 遍历两个链表获取链表的长度len1、len2，同时记录两个链表最后一个节点end1、end2。

2. 如果 end1 != end2，说明不相交返回null即可，如果相等进入第4步。

3. 如果链表1比2长则表1先走 len1 - len2 步，反之表2先走 len2 - len1 步。两个链表第一次走到一起的那个节点即为第一个相交点。

 1 public Node noLoop(Node head1, Node head2)
 2 {
 3     if(head1 == null || head2 == null)
 4         return null;
 5 
 6     Node cur1 = head1, cur2 = head2;
 7     int len = 1;
 8     while(cur1 != null)
 9     {
10         cur = cur.next;
11         len++;
12     }
13     while(cur2 != null)
14     {
15         cur2 = cur2.next;
16         len--;
17     }
18 
19     cur1 = len > 0 ? head1 : head2;
20     cur2 = cur1 == head1 ? head2 : head1;
21     len = Math.abs(len);
22     while(len != 0)
23     {
24         len--;
25         cur1 = cur1.next;
26     }
27 
28     while(cur1 != cur2)
29     {
30         cur1 = cur1.next;
31         cur2 = cur2.next;
32     }
33     return cur1;
34 }

问题三：

1. 如果 loop1 = loop2，那么两个链表形式如图

类似于问题二，只不过我们将loop1（loop2）作为终点。

2. 如果 loop1 != loop2，两个链表相交如图

让表1从 loop1 出发，如果 loop1 之前并没有遇到 loop2，说明两个链表是不相交的，如果遇到了 loop2则说明两链表结构如图，此时返回loop1或loop2都可以

 1 public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2)
 2 {
 3     Node cur1 = null, cur2 = null;
 4     
 5     if(loop1 == loop2)
 6     {
 7         cur1 = head1;
 8         cur2 = head2;
 9         int len = 0;
10         while(cur1 != loop1)
11         {
12             len++;
13             cur1 = cur1.next;
14         }
15         while(cur2 != loop2)
16         {
17             len--;
18             cur2 = cur2.next;
19         }
20         cur1 = n > 0 ? head1 : head2;
21         cur2 = cur1 == head1 ? head2 : head1;
22         len = Math.abs(len);
23         while(len != 0)
24         {
25             len--;
26             cur1 = cur.next;
27         }
28         while(cur1 != cur2)
29         {
30             cur1 = cur1.next;
31             cur2 = cur2.next
32         }
33         return cur1;
34     }
35     else
36     {
37         cur1 = loop1.next;
38         while(cur1 != loop1)
39         {
40             if(cur1 == loop2)
41             {
42                 return loop1;
43             }
44             cur1 = cur1.next;
45         }
46     }
47     return null;
48 }

结合上述三种情况，总代码如下

 1 class Node
 2 {
 3     public int data;
 4     public Node next;
 5 
 6     public Node(int data)
 7     {
 8         this.data = data;
 9     }
10 }
11 
12 public Node getIntersectNode(Node head1, Node head2)
13 {
14     if(head1 == null || head2 == null)
15         return null;
16     Node loop1 = getLoopNode(head1);
17     Node loop2 = getLoopNode(head2);
18 
19     if(loop1 == null && loop2 == null)
20     {
21         return noLoop(head1, head2);
22     }
23     else if(loop1 != null && loop2 != null)
24     {
25         return bothLoop(head1, loop1, head2, loop2);
26     }
27     return null;
28 }

参考资料：程序员代码面试指南 IT名企算法与数据结构题目最优解，左程云