首页 > 代码库 > 判断两个单向链表是否有相交,并找出交点。
判断两个单向链表是否有相交,并找出交点。
分析:
若相交,则两个链表呈Y型,最后一个结点肯定相同;找交点,则用长的链表减去短的,从与短的链表长度想等处开始,两个链表每次移动一个结点,直到相交则是交点。
代码:
NODE* FindNode(NODE* pHead1, NODE* pHead2) { NODE* p1 = pHead1; NODE* p2 = pHead2; int i = 1, j = 1, k = 0, f = 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; } else { p1 = pHead1; p2 = pHead2; f = fabs(i, j); if(i > j) { for(k=0; k<f; k++) { p1 = p1->next; } while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } else { for(k=0; k<f; k++) { p2 = p2->next; } while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } } }
判断两个单向链表是否有相交,并找出交点。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。