判断两个链表是否相交（考虑带环与不带环）_判断两个链表是否相交是否有环

1.不考虑带环的情况，若相交，求交点

解法一：如果两个链表都无环，则可以把第二个链表接在第一个链表后面，如果得到的链表有环，则说明这两个链表相交。这里如果有环，则第二个链表的表头一定在环上，只需要从第二个链表开始遍历，看是否会回到起点即可判断。假设两个链表长度分别为m和n，则时间复杂度为O(m+n)

解法二：若两个链表都无环且交于一点，那么最后一个节点一定是共有的。可以先遍历第一个链表，记录最后一个节点，再遍历第二个链表，将其最后一个节点与第一个链表的最后一个节点比较，若相同，则相交。时间复杂度也为O(m+n)。
代码如下：（结点的结构体）

typedef int DataType;   //结点的结构体
typedef struct LinkNode  
{
    DataType data;
    LinkNode* next;
}Node,*pNode;
1
2
3
4
5
6

bool IsCrossLink(pNode pHead1, pNode pHead2) //判断两链表是否相交(假设链表不带环)
{
    if (pHead1==NULL || pHead2==NULL)
        return false;
    pNode pH1 = pHead1;
    pNode pH2 = pHead2;
    
1
2
3
4
5
6
7