如何判断两个链表是否相交并求出相交点_判断链表是否有相交,若有返回相交节点

排除链表存在环的情况

此情况的意思就是普通的单链表是否相交问题。

相交是什么意思？注意不是单纯的节点的数值域相等，相交的意思是两个链表的部门节点的是同一个，就是这些节点为这两个链表共有。

链表的定义参照：http://blog.csdn.net/dawn_after_dark/article/details/73610674

方法一

我们根据上图可以发现，链表相交之后，后面的部分节点全部共用，所以我们可以用2个指针分别从这两个链表头部走到尾部，最后判断尾部指针的地址信息是否一样，若一样则代表链表相交！
代码：

Node* LinkList::findByIndex(int index){  //根据索引返回节点信息
    Node* p = head;
    int i = 0;
    if (index<0||index >getLength()) {
        cout << "索引非法！" << endl;
        return NULL;
    }
    while (p) {
        if (i == index) 
            return p;
        else {
            p = p->next;
            i++;
        }
    }
    return NULL;
}

bool LinkList::isIntersect(LinkList preLinkList, LinkList forLinkList) {
    Node* tail1 = preLinkList.findByIndex(preLinkList.head->value);//链表1尾部
    Node* tail2 = forLinkList.findByIndex(forLinkList.head->value);//链表2尾部
    if (tail1 == tail2) {
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

方法二

我们可以把其中一个链表的所有节点地址信息存到数组中，然后把另一个链表的每一个节点地址信息遍历数组，若相等，则跳出循环，说明链表相交。进一步优化则是进行hash排序，建立hash表。

方法三

因为我们从上图得知，相交之后部分的长度是相等的，所以我们让长链表的长度减去短链表的长度，得到相差的长度，之后让长链表从头结点开始走过这个长度，与短链表同时向后走，若指针相等，则链表相交；若走到NULL，则链表不相交。
代码：

bool LinkList::isIntersect(LinkList preLinkList, LinkList forLinkList) {
    bool flag = false;
    if (preLinkList.head->value > forLinkList.head->value)
        flag = 
1
2
3
4