判断两个单链表是否相交及找到第一个交点

我不是女神ヾ 2022-06-03 08:56 155阅读 0赞

题目：给两个单链表，如何判断两个单链表是否相交？若相交，则找出第一个相交的节点。  
这道题的思路和解法有很多，在这把这道题的解法做一个详细的总结。

--------------------

解这道题之前，我们需要首先明确一个概念：  
如果两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束。  
因为两个链表中有一个共同节点，则这个节点里的指针域指向的下一个节点地址一样，所以下一个节点也会相交，依次类推。所以，若相交，则两个链表呈“Y”字形。如下图：

![这里写图片描述][SouthEast]

1.暴力解法。  
从头开始遍历第一个链表，遍历第一个链表的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点。若第一个链表遍历结束后，还未找到相同的节点，即不存在交点。时间复杂度为O(n^2)。这种方法显然不是写这篇博客的重点。。。不多说了。

2.使用栈。  
我们可以从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点。每遍历到一个节点时，就将该节点入栈。两个链表都入栈结束后。则通过top判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道，若两个链表相交，则从第一个相交节点开始，后面的节点都相交。  
若两链表相交，则循环出栈，直到遇到两个出栈的节点不相同，则这个节点的后一个节点就是第一个相交的节点。

node temp=NULL;  //存第一个相交节点
    
    while(!stack1.empty()&&!stack1.empty())  //两栈不为空
    {
        temp=stack1.top();  
        stack1.pop();
        stack2.pop();
        if(stack1.top()!=stack2.top())
        {
            break;
        }
    }

这个方法在没有要求空间复杂度的时候，使用栈来解决这个问题也是挺简便的。

3.遍历链表记录长度。  
同时遍历两个链表到尾部，同时记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。  
有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为len1,短的链表长度为len2。  
则先让较长的链表向后移动(len1-len2)个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。  
![这里写图片描述][SouthEast 1]

代码示例:

typedef struct node_t
    {
        int data;//data
        struct node_t *next; //next
    }node;
    
    node* find_node(node *head1, node *head2)
    {
        //链表带头节点
        if(head1==NULL || head2==NULL)
        {
            return NULL;//如果有为空的链表，肯定是不相交的
        }
        node *p1, *p2;
        p1 = head1;
        p2 = head2;
        int len1 = 0;
        int len2 =0;
        int diff = 0;
        while(p1->next!=NULL)
        {
            p1 = p1->next;
            len1++;
        }
        while(p2->next!=NULL)
        {
            p2 = p2->next;
            len2++;
        }
        if(p1 != p2) //如果最后一个节点不相同,返回NULL
        {
            return NULL;
        }
        diff = abs(len1 - len2);
        if(len1 > len2)
        {
            p1 = head1;
            p2 = head2;
        }
        else
        {
            p1 = head2;
            p2 = head1;
        }
        for(int i=0; i<diff; i++)
        {
            p1 = p1->next;
        }
        while(p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }

这个方法也非常的简便并且额外的空间开销很小。时间复杂度为O(len1+len2)。

4.哈希表法。

既然连个链表一旦相交，相交节点一定有相同的内存地址，而不同的节点内存地址一定是不同的，那么不妨利用内存地址建立哈希表，如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是：遍历第一个链表，并利用地址建立哈希表，遍历第二个链表，看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。  
我们可以采用除留取余法构造哈希函数。  
构造哈希表可以采用链地址法解决冲突。哈希表冲突指对key1 != key2，存在f(key1)=f(key2)，链地址法就是把key1和key2作为节点放在同一个单链表中，这种表称为同义词子表，在哈希表中只存储同义词子表的头指针，如下图：

![这里写图片描述][SouthEast 2]

示例代码就不列举了，感兴趣的可以自己写写。

时间复杂度O(length1 + length2)。

5.问题转化为判断一个链表是否有环问题。

这个问题我们可以转换为另一个等价问题：如何判断一个单链表是否有环，若有环，找出环的入口？  
如何转化？  
先遍历第一个链表到它的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表。若该链表有环，则原两个链表一定相交。否则，不相交。  
这样进行转换后就可以从链表头部进行判断了，其实并不用。通过简单的了解我们就很容易知道，如果新链表是有环的，那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的，从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。  
看了下面的示例图就明白了：

![这里写图片描述][SouthEast 3]

知道了转化的方法后，那么重点的问题来了。我们如何判断一个链表是否有环，如何找到环的入口？  
判断是否有环，我们一般容易想到的方法就是记录每个节点是否被访问过，若一个节点被访问了两次，则该链表一定有环。

其实来有一个更为巧妙的方法！

(1)判断链表是否存在环  
设置两个链表指针fast, slow，初始值都指向链表头结点，然后两个指针都往后走，不同的是slow每次前进一步，即前进一个节点。fast每次前进两步，如果存在环，两个指针必定相遇。  
因为只有存在环的情况，我们才可能出现走的快的指针能再次遇到慢的指针。  
并且还有一点就是，若该链表存在环，则在慢指针还没走完一整个环的路程之前，两指针已经相遇。  
为什么？因为从慢指针进入环入口开始计时，慢指针走完一圈的时间，此时快指针已经走了两圈。所以在慢指针走完一圈之前，两指针一定会相遇。

(2)若链表有环，找到环的入口点  
由(1)我们可以知道，当fast与slow相遇时，slow还没走完链表，而fast已经在环内循环了n圈了。  
如图：  
![这里写图片描述][SouthEast 4]

我们把两指针相遇点记为O。则慢指针已走的环路程记为x，环剩下的路程记为y。  
设slow在相遇前走了s步，则fast走了2s步，设环长为r，有2s=s+nr，即s=nr。

由上图可知a+x=s, x+y=r，而我们的目标是找到a的位置。a+x=s=nr=(n-1)r+r=(n-1)r+y+x，则a=(n-1)r+y. 这个公式告诉我们，从链表头和相遇点O分别设一个指针，每次各走一步，这两个指针必定相遇，且相遇的第一个点为环入口点。

示例代码如下：

struct Link  
    {  
        int data;  
        Link *next;  
    };  
    
    // 插入节点 
    void insertNode(Link *&head, int data)  
    {  
        Link *node = new Link;  
        node->data = data;  
        node->next = head;  
        head = node;  
    }  
    
    // 判断链表是否存在环 
    Link* hasCycle(Link* head)  
    {  
        Link *fast, *slow;  
        slow = fast = head;  
        while (fast && fast->next)  
        {  
            fast = fast->next->next;  
            slow = slow->next;  
            if (fast == slow)  
                return slow;  
        }  
        return NULL;  
    }  
    
    // 确定环的入口点,pos表示fast与slow相遇的位置 
    Link* findCycleEntry(Link* head, Link* pos)  
    {  
        while (head != pos)  
        {  
            head = head->next;  
            pos = pos->next;  
        }  
        return head;  
    }

### **扩展问题：如何判断两个存在环的单链表是否相交?如何找出第一个交点？** ###

通过方法(1)我们能够分别找出两个链表的相遇点pos1, pos2，然后还是使用两个指针fast和slow，都初始化为pos1，且fast每次前进2步，slow每次前进1步。若fast指针在遇到slow前，出现fast等于pos2或fast->next等于pos2，则说明两个链表相交，否则不相交。

若两链表相交，我们可知pos2肯定是两个链表的一个相交点，将这个点看做两个链表的终止节点，使用我们上面提到的记录链表长度的解法，即可找到两个链表相交的第一个节点。

并且需要提示一点的是，如果两个带有环的链表相交，则这两个链表的环肯定是同一个环。  
想不通的话可以在纸上画画，你会发现若相交，只会出现这一种情况。

代码示例：

// 判断链表是否存在环
    Link* hasCycle(Link* head)
    {
        Link *fast, *slow;
        slow = fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                return slow;
        }
        return NULL;
    }
    
    Link* findFirstCross(Link* head1, Link* head2)
    {
        Link* pos1 = hasCycle(head1);  
        Link* pos2 = hasCycle(head2); 
    
        // 两个链表都有环
        if (pos1 && pos2)
        {
            // 判断这两个环是不是同一个环
            Link *tmp = pos1;
            do
            {
                if (pos1 == pos2 ||pos1->next == pos2)
                    break;
                pos1 = pos1->next->next;
                tmp = tmp->next;
            }while (pos1!=tmp);
            // 两个链表的环不是同一个环,所以没有交点
            if (pos1 != pos2 && pos1->next != pos2)
                return NULL;
            // 两个链表有共同的交点pos1,现在求第一个交点
            int len1, len2;
            len1 = len2 = 0;
            Link *nd1, *nd2;
            nd1 = head1;
            while (nd1 != pos1) {len1++;nd1=nd1->next;}
            nd2 = head2;
            while (nd2 != pos1) {len2++;nd2=nd2->next;}
            // 较长链表的链表的nd先走dif步
            int dif;
            nd1 = head1; nd2 = head2;
            if (len1 >= len2)
            {
                dif = len1 - len2;
                while (dif--) nd1 = nd1->next;
            }
            else
            {
                dif = len2 - len1;
                while (dif--) nd2 = nd2->next;
            }
            // 之后两个nd再一起走,直到nd相等(即为第一个交点)
            while (nd1!=pos1 && nd2!=pos1)
            {
                if (nd1 == nd2)
                    return nd1;
                nd1 = nd1->next;
                nd2 = nd2->next;
            }
            return pos1;
        }
    }

[SouthEast]: /images/20220603/2c2df8ee5d5643fd92a9ca334d858574.png
[SouthEast 1]: /images/20220603/ab56b155ce9b472d9a7a67e00e924c1e.png
[SouthEast 2]: /images/20220603/c35921e1742041fa9f9efb5e76493a78.png
[SouthEast 3]: /images/20220603/3321fb6f359444b5989ec86dd5a849b5.png
[SouthEast 4]: /images/20220603/dbf58cf311bf456489690efebf321189.png