# 【左神人算法课】超经典：求两单向链表交点（6种情况）

www.MyException.Cn  网友分享于：2013-08-22  浏览：0次
【左神算法课】超经典：求两单向链表交点（6种情况）

### 思路：

这道题实在是太经典，一道题里面考察了几个知识点：

１．链表是否有环的判断

２．链表若有环，要找到环的入口节点

３．两个链表的多种情况分析

另外，左老师讲得实在是太赞了．

### 程序（详解在后面）：

```  1 //C++版，重写了左老师的Java版
2 #include <iostream>
3 using namespace std;
4
6 struct ListNode
7 {
8     int val;
9     ListNode* next;
10     ListNode(int x) : val(x), next(NULL) {}
11 };
12
15         return NULL;
18     while (pSlow != pFast) {
19         if (NULL == pFast->next || NULL == pFast->next->next) {
20             return NULL;
21         }
22         pSlow = pSlow->next;
23         pFast = pFast->next->next;
24     }
26     while (pSlow != pFast) {
27         pSlow = pSlow->next;
28         pFast = pFast->next;
29     }
30     return pSlow;//Or pFast
31 }
32
35         return NULL;
36     }
39     int n = 0;
40     while (NULL != cur1->next) {
41         ++n;
42         cur1 = cur1->next;
43     }
44     while (NULL != cur2->next) {
45         --n;
46         cur2 = cur2->next;
47     }
48     if (cur1 != cur2) { //tail node
49         return NULL;
50     }
53     n = abs(n);
54     while (n--) {
55         cur1 = cur1->next;
56     }
57     while (cur1 != cur2) {
58         cur1 = cur1->next;
59         cur2 = cur2->next;
60     }
61     return cur1;//Or cur2
62 }
63
65     ListNode* cur1 = NULL;
66     ListNode* cur2 = NULL;
67     if (loop1 == loop2) {
70         int n = 0;
71         while (cur1 != loop1) {
72             ++n;
73             cur1 = cur1->next;
74         }
75         while (cur2 != loop2) {
76             --n;
77             cur2 = cur2->next;
78         }
81         n = abs(n);
82         while (n--) {
83             cur1 = cur1->next;
84         }
85         while (cur1 != cur2) {
86             cur1 = cur1->next;
87             cur2 = cur2->next;
88         }
89         return cur1;//Or cur2
90     }
91     else {
92         cur1 = loop1->next;
93         while (cur1 != loop1) {
94             if (cur1 == loop2) {
95                 return loop1;
96             }
97             cur1 = cur1->next;
98         }
99         return NULL;
100     }
101 }
102
105         return NULL;
108     if (NULL == loop1 && NULL == loop2)
110     if (NULL != loop1 && NULL != loop2)
112     return NULL;//one of them have loop,so have no intersectionNode
113 }
114
115 int main() {
116     // 1->2->3->4->5->6->7->null
117     ListNode* head1 = new ListNode(1);
124
125     // 0->9->8->6->7->null
126     ListNode* head2 = new ListNode(0);
131
132
133     // 1->2->3->4->5->6->7->4...
142
143     // 0->9->8->2...
149
150     // 0->9->8->6->4->5->6...
156
157     return 0;
158 }```

```  1 //Java版．左老师给出的代码，很赞
2 //package problems_2017_08_16;
3
4 public class Problem_03_FindFirstIntersectNode {
5
6     public static class Node {
7         public int value;
8         public Node next;
9
10         public Node(int data) {
11             this.value = data;
12         }
13     }
14
17             return null;
18         }
21         if (loop1 == null && loop2 == null) {
23         }
24         if (loop1 != null && loop2 != null) {
26         }
27         return null;
28     }
29
30     public static Node getLoopNode(Node head) {
32             return null;
33         }
34         Node n1 = head.next; // n1 -> slow
35         Node n2 = head.next.next; // n2 -> fast
36         while (n1 != n2) {
37             if (n2.next == null || n2.next.next == null) {
38                 return null;
39             }
40             n2 = n2.next.next;
41             n1 = n1.next;
42         }
44         while (n1 != n2) {
45             n1 = n1.next;
46             n2 = n2.next;
47         }
48         return n1;
49     }
50
53             return null;
54         }
57         int n = 0;
58         while (cur1.next != null) {
59             n++;
60             cur1 = cur1.next;
61         }
62         while (cur2.next != null) {
63             n--;
64             cur2 = cur2.next;
65         }
66         if (cur1 != cur2) {
67             return null;
68         }
71         n = Math.abs(n);
72         while (n != 0) {
73             n--;
74             cur1 = cur1.next;
75         }
76         while (cur1 != cur2) {
77             cur1 = cur1.next;
78             cur2 = cur2.next;
79         }
80         return cur1;
81     }
82
83     public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
84         Node cur1 = null;
85         Node cur2 = null;
86         if (loop1 == loop2) {
89             int n = 0;
90             while (cur1 != loop1) {
91                 n++;
92                 cur1 = cur1.next;
93             }
94             while (cur2 != loop2) {
95                 n--;
96                 cur2 = cur2.next;
97             }
100             n = Math.abs(n);
101             while (n != 0) {
102                 n--;
103                 cur1 = cur1.next;
104             }
105             while (cur1 != cur2) {
106                 cur1 = cur1.next;
107                 cur2 = cur2.next;
108             }
109             return cur1;
110         } else {
111             cur1 = loop1.next;
112             while (cur1 != loop1) {
113                 if (cur1 == loop2) {
114                     return loop1;
115                 }
116                 cur1 = cur1.next;
117             }
118             return null;
119         }
120     }
121
122     public static void main(String[] args) {
123         // 1->2->3->4->5->6->7->null
124         Node head1 = new Node(1);
131
132         // 0->9->8->6->7->null
133         Node head2 = new Node(0);
138
139         // 1->2->3->4->5->6->7->4...
148
149         // 0->9->8->2...
155
156         // 0->9->8->6->4->5->6..
163
164     }
165
166 }```

### 详解

先把几种情况罗列一下：

然后照着程序执行流程梳理思路：

０．判断两链表是否有环（分别找环入口结点，能找到则有环，否则无环）：

若都无环，转入第１步（可能是情况1或2）；

若都有环，转入第２步（可能是情况4或5或6）；

若一个有环一个无环，直接返回NULL，因为如果他们相交，是不可能一个有环一个无环的（图中情况3）；

1.0 先判断两条链表的长度；

1.1 从头节点开始走，更长的链表先走＂长度之差＂步，然后一起走，如果相遇，则为入口点（情况2）；否则无交点（情况1）

２．都有环的情况，这种情况还要细分:

2.0 先判断两链表环入口点是否相同，若相同，则为情况4，转入步骤2.1；若不同，则为情况5或6，转入2.2；

2.1 如果为上图中情况4，我们可以把两链表交点作为＂假想的尾部节点＂，然后就退化成两个无环链表找交点的问题了；

2.2 为判断两链表是否有交点，我们可以从第一个环的入口节点的下一个节点开始next，如果遇到了第二个链表环的入口节点，则返回第一个链表的入口节点（情况5：题目说找出第一个相交的节点，其实我觉得返回第二个链表的入口节点也行）；反之，若走了一圈没遇到第二个链表环的入口节点，说明两链表不相交（情况6）；

至此，程序执行结束．设计很巧妙，要熟练掌握．