首页 > 代码库 > 【编程题目】编程判断俩个链表是否相交
【编程题目】编程判断俩个链表是否相交
第 7 题（链表）
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
看到这个题目我很困惑。如果链表的结构是下面这个样子
typedef struct ListNode{ int m_Value; ListNode * p_Next;}ListNode;
那么一旦有相交，链表的后端就都是一模一样的了啊？因为交叉点只可能有一个p_Next，那只要判断两个链表最后一个不为空的结点是否相同就可以了。
对有环列的，那环只能出现在链表最后面了。扩展的第1、2问只要对两个链表做两层循环判断就可以了。
但总觉得我理解的不对。对于带环链表的创建我也有点困惑。
/*第 7 题（链表）微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?start time = 11:10end time = */#include <stdio.h>#include <stdlib.h>typedef struct ListNode{ int m_Value; ListNode * p_Next;}ListNode;void addNode(ListNode * &pHead, ListNode * newNode){ if(pHead == NULL) { pHead = (ListNode *)malloc(sizeof(ListNode)); pHead->m_Value = http://www.mamicode.com/newNode->m_Value; pHead->p_Next = newNode->p_Next; } else { ListNode * x = pHead; while(x->p_Next != NULL) { x = x->p_Next; } x->p_Next = (ListNode *)malloc(sizeof(ListNode)); x->p_Next->m_Value = http://www.mamicode.com/newNode->m_Value; x->p_Next->p_Next = newNode->p_Next; }}bool isCross(ListNode * p1, ListNode * p2){ ListNode * x = p1; ListNode * y = p2; while(x != NULL) { while(y != NULL) { if(x == y) { return true; } y = y->p_Next; } x = x->p_Next; }}int main(){ ListNode n1 , n2, n3, n4, n5, n6, n7, n8, n9; n1.m_Value = 1; n1.p_Next = &n2; n2.m_Value = 2; n2.p_Next = &n3; n3.m_Value = 3; n3.p_Next = &n7; n4.m_Value = 4; n4.p_Next = &n5; n5.m_Value = 5; n5.p_Next = &n6; n6.m_Value = 6; n6.p_Next = &n7; n7.m_Value = 7; n7.p_Next = &n8; n8.m_Value = 8; n8.p_Next = &n9; n9.m_Value = 9; n9.p_Next = NULL; bool flag = isCross(&n1, &n4); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。