两个单链表相交的一系列问题

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“两个单链表相交的一系列问题”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

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

【思路】：

　　将本问题拆分成3个子问题：

　　　　1、判断一个链表是否有环

　　　　2、判断两个无环链表相交的问题

　　　　3、判断两个有环链表相交的问题

　　　　4、一个有环一个无环则肯定不相交　　

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　实现及测试代码：

  1 /*
  2  *文件名：list_intersect.cpp
  3  *作者：
  4  *摘要：链表相交的一系列问题
  5  */
  6 
  7 #include <iostream>
  8 #include<stdlib.h>
  9 
 10 using namespace std;
 11 
 12 class Node
 13 {
 14 public:
 15     Node(int data)
 16     {
 17         value = data;
 18         next = NULL;
 19     }
 20 public:
 21     int value;
 22     Node *next;
 23 };
 24 
 25 //找到入环节点
 26 Node* getLoopNode(Node *head)
 27 {
 28     if(NULL == head || NULL == head->next || NULL == head->next->next)
 29         return NULL;
 30     Node *n1 = head->next;
 31     Node *n2 = head->next->next;
 32     while(n1 != n2)
 33     {
 34         if(NULL == n2->next || NULL == n2->next->next)
 35             return NULL;
 36         n2 = n2->next->next;
 37         n1 = n1->next;
 38     }
 39     n2 = head;
 40     while(n1 != n2)
 41     {
 42         n1 = n1->next;
 43         n2 = n2->next;
 44     }
 45     return n1;
 46 }
 47 
 48 //不带环的链表的相交节点
 49 Node* noLoop(Node *head1,Node *head2)
 50 {
 51     if(NULL == head1 || NULL == head2)
 52         return NULL;
 53     Node *cur1 = head1;
 54     Node *cur2 = head2;
 55     int n = 0;
 56     
 57     while(NULL != cur1->next)
 58     {
 59         n++;
 60         cur1 = cur1->next;
 61     }
 62     while(NULL != cur2->next)
 63     {
 64         n--;
 65         cur2 = cur2->next;
 66     }
 67 
 68     if(cur1 != cur2)    //若最后一个节点不想等，则俩链表不相交
 69         return NULL;
 70     
 71     cur1 = n > 0 ? head1 : head2;
 72     cur2 = cur1 == head1 ? head2 : head1;
 73     n = abs(n);
 74     while(0 != n)  //以较短的那个链表为准
 75     {
 76         n--;
 77         cur1 = cur1->next;
 78     }
 79     while(cur1 != cur2)
 80     {
 81         cur1 = cur1->next;
 82         cur2 = cur2->next;
 83     }
 84     return cur1;
 85 }
 86 
 87 //带环链表的相交节点的判断
 88 Node* bothLoop(Node *head1,Node *loop1,Node *head2,Node *loop2)
 89 {
 90     Node *cur1(NULL),*cur2(NULL);
 91     
 92     if(loop1 == loop2)    //与不带环的相交节点的判断一样的
 93     {
 94         cur1 = head1;
 95         cur2 = head2;
 96         int n = 0;
 97         while(cur1 != loop1)
 98         {
 99             n++;
100             cur1 = cur1->next;
101         }
102 
103         while(cur2 != loop2)
104         {
105             n--;
106             cur2 = cur2->next;
107         }
108         cur1 = n > 0 ? head1 : head2;
109         cur2 = cur1 == head1 ? head2 : head1;
110         n = abs(n);
111         while(0 != n)
112         {
113             n--;
114             cur1 = cur1->next;
115         }
116         while(cur1 != cur2)
117         {
118             cur1 = cur1->next;
119             cur2 = cur2->next;
120         }
121         return cur1;
122     }
123     else
124     {
125         cur1 = loop1->next;
126         while(cur1 != loop1)
127         {
128             if(cur1 == loop2)
129                 return loop2;
130             cur1 = cur1->next;
131         }
132         return NULL;
133     }
134 }
135 
136 Node* getIntersectNode(Node *head1,Node *head2)
137 {
138     if(NULL == head1 || NULL == head2)
139         return NULL;
140     Node *loop1 = getLoopNode(head1);
141     Node *loop2 = getLoopNode(head2);
142     if(NULL == loop1 && NULL == loop2)
143         return noLoop(head1,head2);
144     if(NULL != loop1 && NULL != loop2)
145         return bothLoop(head1,loop1,head2,loop2);
146     return NULL;
147 }
148 
149 
150 int main()
151 {
152     Node *head1 = NULL;
153     Node *head2 = NULL;
154     Node *ptr1 = NULL;
155     Node *ptr2 = NULL;
156     Node *head3 = NULL;
157     Node *ptr3 = NULL;
158     for(int i =0;i<4;i++)//构造链表
159     {
160         if(NULL == head1 || NULL == head2)
161         {    
162             head1 = new Node(i);
163             head1->next = NULL;
164             ptr1 = head1;
165             head2 = new Node(i);
166             head2->next = NULL;
167             ptr2 = head2;
168             head3 = new Node(10-i);
169             head3->next = NULL;
170             ptr3 = head3;
171             continue;
172         }
173         ptr1->next = new Node(i);
174         ptr1 = ptr1->next;
175         ptr1->next = NULL;
176         ptr2->next = new Node(i);
177         ptr2 = ptr2->next;
178         ptr2->next = NULL;
179         ptr3->next = new Node(10-i);
180         ptr3 = ptr3->next;
181         ptr3->next = NULL;
182     }
183     //第一：无环不相交
184     if(NULL == getIntersectNode(head1,head2))
185         cout << "Two lists are not intersecting!" << endl;
186     //第二：有环不相交
187     ptr1->next = head1->next;
188     ptr2->next = head2->next;
189     if(NULL == getIntersectNode(head1,head2))
190         cout << "Two lists are not intersecting!" << endl;    
191     //第三：无环相交
192     ptr1->next = head3;
193     ptr2->next = head3;
194     if(NULL != getIntersectNode(head1,head2))
195         cout << "Two lists are intersecting!" << getIntersectNode(head1,head2)->value << endl;
196     //第四有环相交
197     ptr3->next = head3;
198     if(NULL != getIntersectNode(head1,head2))
199         cout << "Two lists are intersecting!" << getIntersectNode(head1,head2)->value << endl;
200     return 0;
201 }

View Code

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。