求两个单向链表的交点

题目：

       给出两个单向链表，判断其是否有交点；如果存在交点，请找出交点

解题思路：

      如果存在交点，则两个链表的节点结构必定是同构的；

      如果存在交点，则两个链表必定程序Y字形，而不可能是X形；

      如果存在交点，两个链表在交点及其之后的部分是一致的-----这点很关键，一致的意思包括两部分：长度和内容。

      基于以上三点，可以给出如下解题算法

解题算法：

struct Node { int data; struct Node * next; }; Node* FixIntersetion(Node* pHead1, Node* pHead2) { Node* p1 = pHead1; Node* p2 = pHead2; int i = 1, j = 1, k = 0, diff = 0; //如果都是空链表，肯定没有交点 if(pHead2 == NULL || pHead2 == NULL) { return NULL; } //获取链表长度 while(p1->next != NULL) { p1 = p1->next; i++; } while(p2->next != NULL) { p2 = p2->next; j++; } //开始判断是否存在交点 if(p1 != p2) {//根据有交点时，两个链表在交点及其之后的部分是公共的，因此，有交点的单链表的尾节点必定相同 return NULL; //如果尾节点不同，直接返回NULL } else //否则寻找第一个相同的节点 { p1=pHead1; p2=pHead2; //使得两者的起始比较位置离尾部的长度一致 if(i>j) { diff=i-j; for(k=0; k<diff; k++) { p1 = p1->next; } } if(i<j) { diff=j-i; for(k=0; k<diff; k++) { p2 = p2->next; } } //开始比对，得出交点 while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } }

解题总结：

      本题的解题思路参考http://www.cnblogs.com/songQQ/archive/2009/12/01/1614661.html中的解法，是对其解题算法的解读之后进行的改写（改写幅度不大）。

附：判断单链表是否存在环

bool FixRing(Node * pHead) { Node * pSlow = pHead ; Node * pFast = pHead; while ( pFast && pFast -> next ) //如果存在环，不存在p-next=NULL的情况 { pSlow = pSlow -> next;//前进一步 pFast = pFast -> next -> next;//前进两步 if ( pSlow == pFast ) break ; } return ! (pFast == NULL || pFast -> next == NULL); }

最后

以上就是寒冷小懒虫为你收集整理的求两个单向链表的交点的全部内容，希望文章能够帮你解决求两个单向链表的交点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。