3.6 判断两个链表是否相交

判断两个链表是否相交，若相交则求其交点（指第一个相交的点）。

思路1，利用计数法：遍历链表1，将其节点的内存地址存入map或者hashmap内。然后遍历链表2，并查询map或者hashmap，判断链表2节点是否在里面。若存在，则两者相交，且交于此节点。此方法时间复杂度是O(Length(List1)+Length(List2))且需要O(Length(List1))的空间存储hashmap。如下面代码的isCross_method1

思路2，计数法优化：我们知道，若两链表相交，则交点之后的链表均为两链表所共有。因此，若两者相交，则两者最后的节点一定相同。所以只需要比较两链表最后的节点即可。此方法虽然时间复杂度也为O(Length(List1)+Length(List2))，但只需要O(1)个空间存储最后一个节点就可以。至于求交点，则需要直到两链表的长度（假设Length1>Length2），链表1先走Length1-Length2步，再同时开始走，直到节点相同的点，就是交点。然后如下面代码的isCross_method2

思路3，人为构造环：将链表1的尾节点指向链表2的头节点。问题变为，判断此新链表是否有环，并求环入口点。相关问题可参照这里解决。

需要注意的是判断结束后要将两链表分开。

全部代码如下：

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <hash_map>
  4 
  5 using namespace std;
  6 
  7 const int LONG_LENGTH = 13;
  8 const int SHORT_LENGTH = 4;
  9 
 10 typedef struct node{
 11     int value;
 12     struct node *next;
 13 }node;
 14 
 15 //构造两相交链表，相较于第crossNum个节点。另外为了方便测试, isCross控制两链表是否相交
 16 bool createCrossLink(node *list1,node *list2,int crossNum,bool isCross){
 17     
 18     if(crossNum<0 || crossNum>=LONG_LENGTH) return false;
 19 
 20     node *temp,*last,*longList,*shortList;
 21     longList = list1;
 22     shortList = list2;
 23     //last = (node *)malloc(sizeof(node)); last可以不需要分配内存
 24 
 25     for(int i=LONG_LENGTH-1;i>=0;i--){
 26         node *lp = (node *)malloc(sizeof(node));
 27         lp->value = i;
 28         lp->next = longList->next;
 29         longList->next = lp;
 30         if(i==crossNum){
 31             temp = lp;            //temp是交点
 32         }
 33     }
 34 
 35     for(int i=SHORT_LENGTH-1;i>=1;i--){
 36         node *sp = (node *)malloc(sizeof(node));
 37         sp->value = i*100;
 38         sp->next = shortList->next;
 39         shortList->next = sp;
 40         if(i==SHORT_LENGTH-1){
 41             last = sp;           //last是链表2最后一个节点
 42         }
 43     }
 44 
 45     if(isCross) last->next = temp;
 46     return true;
 47 }
 48 
 49 //遍历链表
 50 void traverse(node *p){
 51     node * ptr = p;
 52     while(ptr!=NULL){
 53         cout<<ptr->value;
 54         if(ptr->next!=NULL) cout<<" -> ";
 55         ptr = ptr->next;
 56     }
 57     cout<<endl;
 58 }
 59 
 60 //思路1，利用hash_map
 61 bool isCross_method1(node *l1,node *l2){
 62 
 63     if(l1==NULL || l2==NULL) return false;
 64 
 65     node *firstPtr,*secondPtr;
 66     firstPtr = l1;
 67     secondPtr = l2;
 68 
 69     hash_map<node *,int> ptrMap;
 70     hash_map<node *,int>::iterator it;
 71 
 72     while(firstPtr!=NULL){
 73         ptrMap.insert(pair<node *,int>(firstPtr,firstPtr->value));
 74         firstPtr = firstPtr->next;
 75     }
 76     
 77     for(it=ptrMap.begin();it!=ptrMap.end();it++){
 78         cout<<(*it).first<<" => "<<(*it).second<<endl;
 79     }
 80 
 81     while(secondPtr!=NULL){
 82         if(ptrMap.find(secondPtr)!=ptrMap.end()){
 83             cout<<"Crossing at: "<<secondPtr<<endl;
 84             return true;
 85         }
 86         secondPtr = secondPtr->next;
 87     }
 88 
 89     return false;
 90 }
 91 
 92 //思路2
 93 bool isCross_method2(node *l1,node *l2){
 94     
 95     if(l1==NULL || l2==NULL) return false;
 96 
 97     node *firstPtr,*secondPtr,*first,*second;
 98     firstPtr = l1;
 99     secondPtr = l2;
100     int firLen = 0;
101     int secLen = 0;
102 
103     while(firstPtr!=NULL){
104         if(firstPtr->next==NULL) first=firstPtr;
105         firstPtr=firstPtr->next;
106         firLen++;
107     }
108     while(secondPtr!=NULL){
109         if(secondPtr->next==NULL) second=secondPtr;
110         secondPtr=secondPtr->next;
111         secLen++;
112     }
113 
114     if(first==second){  //判断尾节点是否相等
115         firstPtr = l1;  //要将指针重新指向两节点的头节点，再开始找交点！
116         secondPtr = l2;
117         if(firLen>secLen){
118             for(int i=0;i<firLen-secLen;i++){
119                 firstPtr = firstPtr->next;
120             }
121         }else{
122             for(int i=0;i<secLen-firLen;i++){
123                 secondPtr = secondPtr->next;
124             }
125         }
126 
127         while(firstPtr!=secondPtr){
128             firstPtr=firstPtr->next;
129             secondPtr = secondPtr->next;
130         }
131 
132         cout<<"Crossing at: "<<firstPtr<<":"<<firstPtr->value<<" , "<<secondPtr<<":"<<secondPtr->value<<endl;
133         return true;
134     }else 
135         return false;
136 }
137 
138 int _tmain(int argc, _TCHAR* argv[])
139 {
140     node *longHead = (node *)malloc(sizeof(node));
141     node *shortHead = (node *)malloc(sizeof(node));
142     longHead->next = NULL;
143     shortHead->next = NULL;
144 
145     if(createCrossLink(longHead,shortHead,6,true)){
146         traverse(longHead->next);
147         traverse(shortHead->next);
148 
149         cout<<isCross_method1(longHead->next,shortHead->next)<<endl;;
150         cout<<endl;
151         cout<<isCross_method2(longHead->next,shortHead->next)<<endl;;
152     }
153 
154     return 0;
155 }

以上均假设两链表无环，如不知两者是否有环，则需要分步骤解决：

1. 若两者均无环，按上述思路解决

2. 若一个有环，一个无环，则两者不相交（因为不可能无环链表与有环链表相交，这样无环链表也会变有环）

3. 若两者皆有环，则可求出链表1的入口节点是否在链表2的环中，若在则相交。相交时环必为两者共有。

环相关问题，请参考这里

参考：

http://blog.csdn.net/liuxialong/article/details/6556096