赞
踩
解法一:如果两个链表都无环,则可以把第二个链表接在第一个链表后面,如果得到的链表有环,则说明这两个链表相交。这里如果有环,则第二个链表的表头一定在环上,只需要从第二个链表开始遍历,看是否会回到起点即可判断。假设两个链表长度分别为m和n,则时间复杂度为O(m+n)
解法二:若两个链表都无环且交于一点,那么最后一个节点一定是共有的。可以先遍历第一个链表,记录最后一个节点,再遍历第二个链表,将其最后一个节点与第一个链表的最后一个节点比较,若相同,则相交。时间复杂度也为O(m+n)。
代码如下:(结点的结构体)
typedef int DataType; //结点的结构体
typedef struct LinkNode
{
DataType data;
LinkNode* next;
}Node,*pNode;
bool IsCrossLink(pNode pHead1, pNode pHead2) //判断两链表是否相交(假设链表不带环)
{
if (pHead1==NULL || pHead2==NULL)
return false;
pNode pH1 = pHead1;
pNode pH2 = pHead2;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。