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

xiaoxi666

发布于 2018-10-29 17:32:01

66000

代码可运行

文章被收录于专栏：xiaoxi666的专栏xiaoxi666的专栏

运行总次数：0

代码可运行

题目描述：

思路：

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

　　　　１．链表是否有环的判断

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

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

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

程序（详解在后面）：

  1 //C++版，重写了左老师的Java版
  2 #include <iostream>
  3 using namespace std;
  4 
  5 //definition for singly-linked list.
  6 struct ListNode
  7 {
  8     int val;
  9     ListNode* next;
 10     ListNode(int x) : val(x), next(NULL) {}
 11 };
 12 
 13 ListNode* getLoopNode(ListNode* head) {
 14     if (NULL == head || NULL == head->next || NULL == head->next->next)
 15         return NULL;
 16     ListNode* pSlow = head->next;
 17     ListNode* pFast = head->next->next;
 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     }
 25     pFast = head; //walk again to head,and speed equal.Or pSlow
 26     while (pSlow != pFast) {
 27         pSlow = pSlow->next;
 28         pFast = pFast->next;
 29     }
 30     return pSlow;//Or pFast
 31 }
 32 
 33 ListNode* noLoop(ListNode* head1, ListNode* head2) {
 34     if (NULL == head1 || NULL == head2) {
 35         return NULL;
 36     }
 37     ListNode* cur1 = head1;
 38     ListNode* cur2 = head2;
 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     }
 51     cur1 = n > 0 ? head1 : head2;
 52     cur2 = cur1 == head1 ? head2 : head1;
 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 
 64 ListNode* bothLoop(ListNode* head1, ListNode*loop1, ListNode* head2, ListNode*loop2) {
 65     ListNode* cur1 = NULL;
 66     ListNode* cur2 = NULL;
 67     if (loop1 == loop2) {
 68         cur1 = head1;
 69         cur2 = head2;
 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         }
 79         cur1 = n > 0 ? head1 : head2;
 80         cur2 = cur1 == head1 ? head2 : head1;
 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 
103 ListNode* getIntersectNode(ListNode* head1, ListNode* head2) {
104     if (NULL == head1 || NULL == head2)
105         return NULL;
106     ListNode* loop1 = getLoopNode(head1);
107     ListNode* loop2 = getLoopNode(head2);
108     if (NULL == loop1 && NULL == loop2)
109         return noLoop(head1, head2);
110     if (NULL != loop1 && NULL != loop2)
111         return bothLoop(head1, loop1, head2, 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);
118     head1->next = new ListNode(2);
119     head1->next->next = new ListNode(3);
120     head1->next->next->next = new ListNode(4);
121     head1->next->next->next->next = new ListNode(5);
122     head1->next->next->next->next->next = new ListNode(6);
123     head1->next->next->next->next->next->next = new ListNode(7);
124 
125     // 0->9->8->6->7->null
126     ListNode* head2 = new ListNode(0);
127     head2->next = new ListNode(9);
128     head2->next->next = new ListNode(8);
129     head2->next->next->next = head1->next->next->next->next->next; // 8->6
130     cout << getIntersectNode(head1, head2)->val << endl;
131 
132 
133     // 1->2->3->4->5->6->7->4...
134     head1 = new ListNode(1);
135     head1->next = new ListNode(2);
136     head1->next->next = new ListNode(3);
137     head1->next->next->next = new ListNode(4);
138     head1->next->next->next->next = new ListNode(5);
139     head1->next->next->next->next->next = new ListNode(6);
140     head1->next->next->next->next->next->next = new ListNode(7);
141     head1->next->next->next->next->next->next->next = head1->next->next->next;// 7->4
142 
143     // 0->9->8->2...
144     head2 = new ListNode(0);
145     head2->next = new ListNode(9);
146     head2->next->next = new ListNode(8);
147     head2->next->next->next = head1->next; // 8->2
148     cout << getIntersectNode(head1, head2)->val << endl;
149 
150     // 0->9->8->6->4->5->6...
151     head2 = new ListNode(0);
152     head2->next = new ListNode(9);
153     head2->next->next = new ListNode(8);
154     head2->next->next->next = head1->next->next->next->next->next; // 8->6
155     cout << getIntersectNode(head1, head2)->val << endl;
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 
 15     public static Node getIntersectNode(Node head1, Node head2) {
 16         if (head1 == null || head2 == null) {
 17             return null;
 18         }
 19         Node loop1 = getLoopNode(head1);
 20         Node loop2 = getLoopNode(head2);
 21         if (loop1 == null && loop2 == null) {
 22             return noLoop(head1, head2);
 23         }
 24         if (loop1 != null && loop2 != null) {
 25             return bothLoop(head1, loop1, head2, loop2);
 26         }
 27         return null;
 28     }
 29 
 30     public static Node getLoopNode(Node head) {
 31         if (head == null || head.next == null || head.next.next == null) {
 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         }
 43         n2 = head; // n2 -> walk again from head
 44         while (n1 != n2) {
 45             n1 = n1.next;
 46             n2 = n2.next;
 47         }
 48         return n1;
 49     }
 50 
 51     public static Node noLoop(Node head1, Node head2) {
 52         if (head1 == null || head2 == null) {
 53             return null;
 54         }
 55         Node cur1 = head1;
 56         Node cur2 = head2;
 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         }
 69         cur1 = n > 0 ? head1 : head2;
 70         cur2 = cur1 == head1 ? head2 : head1;
 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) {
 87             cur1 = head1;
 88             cur2 = head2;
 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             }
 98             cur1 = n > 0 ? head1 : head2;
 99             cur2 = cur1 == head1 ? head2 : head1;
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);
125         head1.next = new Node(2);
126         head1.next.next = new Node(3);
127         head1.next.next.next = new Node(4);
128         head1.next.next.next.next = new Node(5);
129         head1.next.next.next.next.next = new Node(6);
130         head1.next.next.next.next.next.next = new Node(7);
131 
132         // 0->9->8->6->7->null
133         Node head2 = new Node(0);
134         head2.next = new Node(9);
135         head2.next.next = new Node(8);
136         head2.next.next.next = head1.next.next.next.next.next; // 8->6
137         System.out.println(getIntersectNode(head1, head2).value);//output:6
138 
139         // 1->2->3->4->5->6->7->4...
140         head1 = new Node(1);
141         head1.next = new Node(2);
142         head1.next.next = new Node(3);
143         head1.next.next.next = new Node(4);
144         head1.next.next.next.next = new Node(5);
145         head1.next.next.next.next.next = new Node(6);
146         head1.next.next.next.next.next.next = new Node(7);
147         head1.next.next.next.next.next.next.next = head1.next.next.next; // 7->4
148 
149         // 0->9->8->2...
150         head2 = new Node(0);
151         head2.next = new Node(9);
152         head2.next.next = new Node(8);
153         head2.next.next.next = head1.next; // 8->2
154         System.out.println(getIntersectNode(head1, head2).value);//output:2
155 
156         // 0->9->8->6->4->5->6..
157         head2 = new Node(0);
158         head2.next = new Node(9);
159         head2.next.next = new Node(8);
160         head2.next.next.next = head1.next.next.next.next.next; // 8->6
161         System.out.println(getIntersectNode(head1, head2).value);//output:4
162         System.out.println(getIntersectNode(head2, head1).value);//note the order //output:6
163 
164     }
165 
166 }

详解

先把几种情况罗列一下：

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

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

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

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

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

　　１．都无环的情况，退化到两个无环链表找入口点的问题（可参见＜剑指offer＞和leetcode:Intersection of Two Linked Lists）

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

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

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

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

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

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-08-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度