编程之美3.6——编程判断两个链表是否相交

问题：

给出两个单向链表的头指针，而两个链表都可能带环，判断这两个链表是否相交，并且给出他们相交的第一个节点。

解法：参考http://blog.csdn.net/ldong2007/article/details/4544203

(1)判断链表是否存在环

设置两个链表指针(fast, slow)，初始值都指向链表头结点，然后连个指针都往前走，不同的是slow每次前进一步，fast每次前进两步，如果存在环，两个指针必定相遇。

(2)若链表有环，找到环的入口点

当fast与slow相遇时，slow还没走完链表，而fast已经在环内循环了n圈了，假设slow在相遇前走了s步，则fast走了2s步，设环长为r，有2s=s+nr，即s=nr.

由上图可知a+x=s, x+y=r，而我们的目标是找到a的位置。设上图那个拱起的曲线的长度为y，有a+x=s=nr=(n-1)r+r=(n-1)r+y+x，则a=(n-1)r+y. 这个公式告诉我们，从链表头和相遇点分别设一个指针，每次各走一步，这两个指针必定相遇，且相遇的第一个点为环入口点。

(3)若两个链表都不存在环，找出两个链表相交的第一个节点

1. 将其中一个链表首尾相连，判断另一个链表是否存在环，如果存在，则两个链表相交，且找出来的环入口点即为相交的第一个点。

2. 首先遍历两个链表，记下两个链表的长度，长链表从起点先前进len_max-len_min步，然后两个链表再一起前进，每次一步，相遇的第一个点即为相交的第一个点。

(4)若两个链表都存在环，找出两个链表相交的第一个节点

通过方法(1)我们能够分别找出两个链表的相遇点pos1, pos2，然后还是使用两个指针fast和slow，都初始化为pos1，且fast每次前进2步，slow每次前进1步。若fast指针在遇到slow前，出现fast等于pos2或fast->next等于pos2，则说明两个链表相交，否则不相交。若两链表相交，我们可知pos2肯定是两个链表的一个相交点，将这个点看做链表的终止节点，使用方法(3)。

#include <iostream>#include <algorithm>using namespace std;struct Link{int data;Link *next;};// 插入节点void insertNode(Link *&head, int data){Link *node = new Link;node->data = data;node->next = head;head = node;}// 判断链表是否存在环Link* hasCycle(Link* head){Link *fast, *slow;slow = fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow)return slow;}return NULL;}// 确定环的入口点,pos表示fast与slow相遇的位置Link* findCycleEntry(Link* head, Link* pos){while (head != pos){head = head->next;pos = pos->next;}return head;}// 找到两个链表相交的第一个交点（链表可能会有环）Link* findFirstCross(Link* head1, Link* head2){Link* pos1 = hasCycle(head1);Link* pos2 = hasCycle(head2);// 一个链表有环，另一个链表没环，那肯定没有交点if (pos1 && !pos2 || !pos1 && pos2)return NULL;Link *nd1, *nd2;// 两个链表都没有环if (!pos1 && !pos2){// 记下两个链表的长度int len1, len2;len1 = len2 = 0;nd1 = head1;while (nd1) {len1++;nd1=nd1->next;}nd2 = head2;while (nd2) {len2++;nd2=nd2->next;}// 较长链表的链表的nd先走dif步int dif;nd1 = head1; nd2 = head2;if (len1 >= len2){dif = len1 - len2;while (dif--) nd1=nd1->next;}else{dif = len2 - len1;while (dif--) nd2=nd2->next;}// 之后两个nd再一起走,直到某个nd为NULL(不相交)// 或直到nd相等(即为第一个交点)while (nd1 && nd2){if (nd1==nd2)return nd1;nd1=nd1->next;nd2=nd2->next;}return NULL;}// 两个链表都有环if (pos1 && pos2){// 判断这两个环是不是同一个环Link *tmp = pos1;do{if (pos1 == pos2 ||pos1->next == pos2)break;pos1 = pos1->next->next;tmp = tmp->next;}while (pos1!=tmp);// 两个链表的环不是同一个环,所以没有交点if (pos1 != pos2 && pos1->next != pos2)return NULL;// 两个链表有共同的交点pos1,现在求第一个交点int len1, len2;len1 = len2 = 0;Link *nd1, *nd2;nd1 = head1;while (nd1 != pos1) {len1++;nd1=nd1->next;}nd2 = head2;while (nd2 != pos1) {len2++;nd2=nd2->next;}// 较长链表的链表的nd先走dif步int dif;nd1 = head1; nd2 = head2;if (len1 >= len2){dif = len1 - len2;while (dif--) nd1 = nd1->next;}else{dif = len2 - len1;while (dif--) nd2 = nd2->next;}// 之后两个nd再一起走,直到nd相等(即为第一个交点)while (nd1!=pos1 && nd2!=pos1){if (nd1 == nd2)return nd1;nd1 = nd1->next;nd2 = nd2->next;}return pos1;}}int total[] = {8, 2, 5};int C[10] = {15, 14, 13, 12, 11, 10, 9, 8};int B[10] = {7, 6};int A[10] = {5, 4, 3, 2, 1};int main(){Link *headB, *headA;headB = headA = NULL;int i;for (i=0; i<total[0]; i++)insertNode(headB, C[i]);Link *nd = headB;while (nd->next) nd = nd->next;// 8->9->10->11->12->13->14->15->10->11->12->...nd->next = headB->next->next;headA = headB;// B: 6->7->8->9->10->...->15->10->...for (i=0; i<total[1]; i++)insertNode(headB, B[i]);// A: 1->2->3->4->5->8->9->10->...->15->10->...for (i=0; i<total[2]; i++)insertNode(headA, A[i]);// find: 8Link *pos = findFirstCross(headA, headB);if (pos)printf("yes: %d\n", pos->data);elseprintf("no\n");}

1楼han_yankun20092小时前

学习了