判断两个单链表是否相交？若相交求交点？（单链表无环）

50 阅读 0 评论 33 点赞

我是靠谱客的博主年轻鸵鸟，最近开发中收集的这篇文章主要介绍判断两个单链表是否相交？若相交求交点？（单链表无环），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

怎样判断单链表是否相交？
如果两个链表相交，则两个链表就会有相同的结点。
这里写图片描述
方法1. 依次判断第一个链表中的结点是否都在第二个链表中。
方法2. 若两个单链表相交，则从交点之后的链表结点内容是一样的，即两个单链表最后一个结点一定是相同的，我们可以遍历两个结点，判断最后一个元素地址是否相同。
方法3.构环，将L2的最后一个结点指向L2的头结点，构成环，判断L1链表是否有环，若有环则两个单链表相交，若无环则不相交。构环后记得解环

#define DataType int
typedef struct Node{
    DataType data;
   struct Node* next;
}linklist;

void LinklistIntersect(linklist *p1, linklist * p2)
{
    linklist *cur = NULL;
    linklist *cur2 = NULL;
    linklist *fast = NULL;
    linklist *slow = NULL;
    if (p1 == NULL || p2 == NULL)
        return;
    cur2 = cur = p2;
    //构环
    while (cur2->next != NULL)
    {
        cur2 = cur2->next;
    }
    cur2->next = cur;
    //判断是否带环
    fast = slow = p1;
    while (fast != NULL&&fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
        {
            printf("两个单链表相交！n");
            //解环
            cur2->next = NULL;
            //判断交点
            LinkListpoint(p1, p2);
            return;
        }
    }
    printf("两个链表不相交！n");
}

判断两个单链表的交点：
先算两个链表的长度差(count)，长度较长的链表先走长度差(count)步,之后两个链表一起向后移动，直到两个链表结点相同为止，这个结点即就是两个单链表的交点。

void LinkListpoint(linklist *p1, linklist *p2)
{
    int count = 0;
    int count1 = 0;
    int count2 = 0;
    linklist *cur1 = p1;
    linklist *cur2 = p2;
    //p1的长度
    while (cur1 != NULL)
    {
        count1++;
        cur1 = cur1->next;
    }
    //p2的长度
    while (cur2 != NULL)
    {
        count2++;
        cur2 = cur2->next;
    }
    cur1 = p1;
    cur2 = p2;
    //p1与p2的差
    count = count1 - count2;
    if (count >= 0)
    {
        //p1先走count步
        while (count--)
        {
            cur1 = cur1->next;
        }
        while (cur1 != cur2)
        {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        printf("交点为：%dn", cur1->data);
    }
    else
    {
        while (count--)
        {
            cur2 = cur2->next;
        }
        while (cur1 != cur2)
        {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        printf("交点为：%dn", cur1->data);
    }
}