首页 > 代码库 > 链表操作 -- 两个链表间的相交性问题
链表操作 -- 两个链表间的相交性问题
本文参考：
http://blog.csdn.net/g_brightboy/article/details/6824834
http://blog.csdn.net/huangxy10/article/details/8014233
在此致谢。
- 问题：
给定两个链表，判断它们是否相交。
注意：
如果两个链表相交的话，则公用相交点开始往后的所有节点。【因为节点的next指针只有一个！】
解答：
1)首先来看最直观的方法，也就是一次判断链表A中的节点是否在链表B中出现。
时间复杂度：O(n2)
空间复杂度：O(1)
1 bool List::isIntersect(Node* listA,Node* listB){2 for(Node* headA = listA; headA != NULL ; headA = headA->next){3 for(Node* headB = listB; headB != NULL; headB = headB->next){4 if(headA == headB)5 return true;6 }7 } 8 return false; 9 }
2)在方法(1)中，链表A中节点每次都需要匹配链表B中每个节点，这个匹配动作的时间复杂度为O(n)。考虑使用Hash来存储链表B，这样可将匹配动作的时间复杂度降低为O(1)。
时间复杂度：O(n)
空间复杂度：O(n)
1 bool isIntersect(Node* listA,Node* listB){ 2 unordered_map<Node*,bool> hashTable; 3 4 for(Node* tmp = listA; tmp != NULL; tmp=tmp->next) 5 { 6 hashTable.insert(pair<Node*,bool>(tmp,true)); 7 } 8 9 for(Node* tmp = listB; tmp != NULL; tmp=tmp->next)10 {11 unordered_map<Node*,bool>::iterator iter = hashTable.find(tmp);12 if(iter!=hashTable.end() && iter->second)13 return true;14 }15 16 return false;17 }
3)考虑当两个链表相交时，自相交点之后的所有节点都一样。因此，当两个链表的尾节点一样时就是相交的。
时间复杂度：O(n)
空间复杂度：O(1)
1 bool isIntersect(Node* listA,Node* listB) 2 { 3 if(listA==NULL || listB==NULL) 4 return false; 5 6 Node* tailA = listA; 7 while(tailA->next != NULL) 8 tailA = tailA->next; 9 10 Node* tailB = listB;11 while(tailB->next != NULL)12 tailB = tailB->next;13 14 return (tailA == tailB);15 }
4)思考之前处理的 “判断链表是否有环”的问题。 当链表A与链表B相交时，将链表A的首尾相连，则链表B中出现环。
时间复杂度：O(n)
空间复杂度：O(1)
1 bool hasCycle(Node* listB) 2 { 3 if(listB==NULL) 4 return false; 5 6 Node* fast = listB->next; 7 Node* slow = listB; 8 9 while(fast!=NULL && fast->next!=NULL)10 {11 fast = fast->next->next;12 slow = slow->next;13 14 if(fast == slow)15 return true;16 }17 return false;18 }19 20 bool isIntersect(Node* listA,Node* listB)21 {22 if(listA == NULL || listB == NULL)23 return false;24 25 Node* tailA = listA;26 while(tailA->next != NULL)27 tailA = tailA->next;28 29 tailA->next = listA;30 31 return hasCycle(listB); 32 33 }
5)More ?
- 问题
求两个相交链表的第一个交点
解答：
1)将链表A收尾相连，之后“寻找有环链表的首个环节点”
1 Node* find_cycle_begin(Node* list) 2 { 3 Node* fast = list->next; 4 Node* slow = list; 5 6 while(fast != NULL && fast->next !=NULL) 7 { 8 fast = fast->next->next; 9 slow = slow->next;10 11 if(fast == slow)12 break;13 }14 15 fast = fast->next;16 slow = list;17 18 while(fast != slow)19 {20 fast = fast->next;21 slow = slow->next;22 }23 24 return fast;25 }26 27 Node* isIntersect(Node* listA,Node* listB)28 {29 if(listA == NULL)30 return (new Node(-1));31 32 Node* tail = listA; 33 while(tail->next != NULL)34 tail = tail->next;35 36 tail->next = listA;37 38 return find_cycle_begin(listB); 39 }
2)依次比较
可用加速操作：
[1].假设链表A的长度lenA大于链表B的lenBa。在第一个交点的位置一定在链表的后lenB的内。可以不用判断前lenA - lenB个节点。
[2].将链表A的节点存储在hash表中,一次检查链表B中的节点。
链表操作 -- 两个链表间的相交性问题