562-单链表刷题(2)

àì夳堔傛蜴生んèń 2022-09-11 11:13 144阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

## 单链表判断是否有环？找环的入口节点？ ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**如果说这个链表存在环，那么意味着：**  
遍历不到末尾节点了，因为它找不到一个节点的next地址域是空  
**如果找到一个节点的next地址域是空，它就不存在环了。**  
**如果现在18这个节点的next地址域存储的是67的地址**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**此时，遍历链表，访问25,67,32,18,67,32,18…在67-18不断的绕圈**  
**这就是单链表存在环**

**解决方法：**

**方法1**：额外开辟一个内存空间，实现哈希表，然后遍历链表，把节点的地址放入哈希表中，每次存放之前都判断一下是否存在，不存在就把当前节点地址存进去，如果发现要存放的节点的地址在哈希表已经存在了，就说明有环了。第一次发现相同的节点，此时这个节点就是环的入口节点了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
O(n)的空间复杂度

**方法2：**  
**原地解决这个问题！**  
保证最低的时间复杂度和空间复杂度  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**在操场上跑步，有的人跑的很快，有的人跑的很慢，以至于跑的很快的人都比跑的很慢的人快了1圈**

**我们采用双指针的应用**  
快慢指针  
![在这里插入图片描述][dc49d90fae3340198c27ef48d8b75a52.png]  
**快指针跑的快，如果存在环的话，快指针“会赶上”慢指针**  
慢指针一次跑1个节点  
快指针一次跑2个节点  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
它们在头节点开始跑，如果链表不存在环，18这个末尾节点的next地址域为空，那么fast首先跑成空，就不存在环了  
**如果真的存在环的话，最终的结果是fast==low又成立了**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**如果存在环，fast总会赶上low，又一次相遇**  
**在操场一直跑圈，速度快的人总会和速度慢的人再次相遇**

**会不会fast跑了两步刚好把slow越过了，导致fast和slow总是遇不上？？？**  
![在这里插入图片描述][fd64a2ffe7024a859491b4f330e85ecb.png]  
**这种情况是不可能出现的！**  
只有下面这种情况才能说明fast把slow越过去了：  
![在这里插入图片描述][76cc50965b4c49aead4bf31c8f856239.png]  
它俩现在已经在一块了  
然后slow跑1步，fast跑2步  
![在这里插入图片描述][8af75c844e524313a4016260a9a844f3.png]  
这才是fast把slow越过去了  
**但是在走之前，它们两个已经相遇了！**  
所以，这种情况根本不考虑的。

**如何找到环的入口节点？**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
**我们解析一下图中画的4条虚线：**  
第1条线是快慢指针起始的地方，  
第2条线表示环的入口节点，  
第3条线表示快慢指针判断单链表是否存在环，再次相遇的地方  
第4条线表示环的前1个节点  
**我们通过数学推导：**  
我们设x,y,a  
**x表示赛跑的起点到环入口的距离  
y表示环入口到快慢指针相遇点的距离  
a表示快慢指针相遇点到环入口的距离**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
**我们知道 快指针的速度是慢指针的速度的2倍**  
![在这里插入图片描述][485af9639c1246c6a599b680509a85c9.png]  
![在这里插入图片描述][a78b6f94dc3f4923ac2fa9090cca9151.png]  
![在这里插入图片描述][b030e6089bf64b3d8d609a158e86b972.png]  
![在这里插入图片描述][9e384a5dbee04288a5478703d81aae86.png]  
![在这里插入图片描述][03ef762ec407422bb92de19578d075fc.png]  
![在这里插入图片描述][e5781296db8742a8ae7c8b244ac61698.png]  
也就是说，我要找环的入口，从快慢指针再次相遇的地方，**然后再来1个指针指向赛跑的起点位置，即头节点**，然后这个新定义的指针和慢指针同时往后走，一次走1步，因为x=a，**它们相遇的节点就是环的入口节点！！！**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**67节点就是环的入口节点**

//判断单链表是否存在环，存在返回环的入口节点
    bool IsLinkHasCircle(Node *head, int& val)
    {
        
        Node *fast = head;
        Node *slow = head;
    
        while (fast != nullptr && fast->next_ != nullptr)
        {
        
            slow = slow->next_;
            fast = fast->next_->next_;//fast和fast->next都要判空,才能指向next 
    
            if (slow == fast)
            {
        
                //快慢指针再次遇见，链表存在环
                fast = head;//fast回到头节点和slow一起往后走，1次走1个节点 
                while (fast != slow)
                {
        
                    slow = slow->next_;
                    fast = fast->next_;
                }//出while循环，相遇的节点就是环的入口节点 
                val = slow->data_;//把环的入口节点的值带出去 
                return true;
            }
        }
        return false;
    }

测试代码如下：

int main()
    {
        
        Node head;
    
        Node n1(25), n2(67), n3(32), n4(18);
        head.next_ = &n1;
        n1.next_ = &n2;
        n2.next_ = &n3;
        n3.next_ = &n4;
        n4.next_ = &n2;
    
        int val;
        if (IsLinkHasCircle(&head, val))
        {
        
            cout << "链表存在环，环的入口节点是：" << val << endl;
        }
    }

## 判断两个单链表是否相交，返回相交的节点值 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
**如果两个单链表相交，如下图所示：**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
**方法1**：传统的解法，额外开辟空间创建一个哈希表，从第一个链表开始遍历，然后把第一个链表的每个节点地址写进哈希表。  
然后遍历第二个链表，依次比对哈希表中的元素，如果第二个链表中第一次发现有节点的地址和哈希表中存储的节点的地址一样，则这个节点是相交节点，如果遍历完第二个链表，节点都没有和哈希表中的一样，就是这两个链表不相交。

**方法2：**  
原地处理！保证最低的时间复杂度和空间复杂度！  
**我们发现：两个链表从相交的节点到链表的末尾节点，是一样的，共享的！两个链表相交的节点之前的长度是不确定是否相等的！**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
我们先遍历第一个链表，计算出节点的个数：4  
然后遍历第二个链表，计算出节点的个数：3  
这2个链表的长度的差值是1，也就是说，它们不要从头节点开始走。  
**1个指针p指向第1个链表的第1个有效节点  
1个指针q指向第2个链表的头节点  
也就是说，现在p和q离末尾节点的距离是一样的了。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]  
**然后p和q每走1步，判断1下，节点地址是否相等，直到遇到相交节点。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]  
**p和q要是一直走1步，判断1下  
然后它们指向的节点永远不是同一个，最后p和q走向各自链表的尾节点，然后都为空了，那么说明这两个链表不相交**

//判断两个单链表是否相交，如果相交，返回相交节点的值
    bool IsLinkHasMerge(Node* head1, Node* head2, int& val)
    {
        
        int cnt1 = 0, cnt2 = 0;//统计链表的长度（有效节点的个数） 
        Node* p = head1->next_;
        Node* q = head2->next_;
    
        while (p != nullptr)
        {
        
            cnt1++;
            p = p->next_;
        }
    
        while (q != nullptr)
        {
        
            cnt2++;
            q = q->next_;
        }
    
        p = head1;
        q = head2;
        
        //我们让比较长的那个链表先走差值个节点 
        if (cnt1 > cnt2)
        {
        
            //第一个链表长
            int offset = cnt1 - cnt2;
            while (offset-- > 0)
            {
        
                p = p->next_;
            }
        }
        else
        {
        
            //第二个链表长
            int offset = cnt2 - cnt1;
            while (offset-- > 0)
            {
        
                q = q->next_;
            }
        }
    
        while (p != nullptr && q != nullptr)
        {
        
            if (p == q)
            {
        
                val = p->data_;
                return true;
            }
            p = p->next_;
            q = q->next_;
        }
    
        return false;
    }

测试代码如下：

int main()
    {
        
        Node head1;
        Node n1(25), n2(67), n3(32), n4(18);
        head1.next_ = &n1;
        n1.next_ = &n2;
        n2.next_ = &n3;
        n3.next_ = &n4;
    
        Node head2;
        Node n5(31);
        head2.next_ = &n5;
        n5.next_ = &n1;
    
        int val;
        if (IsLinkHasMerge(&head1, &head2, val))
        {
        
            cout << "链表相交，相交节点是：" << val << endl;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0c20ecd455e3401a98b874e16e1fc341.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/1405a3d45e024877a7c6a2eade1fee49.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/2650626d72784a1983b013191c3da15f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/cadfbb311d3b49498478af424596862e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/1ff6769b3c424e7d82b63dcd7ba27d3c.png
[dc49d90fae3340198c27ef48d8b75a52.png]: /images/20220828/9363d772502a43dbb54920eebabcec6c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/a59e3df7408b4893a04add18417e734d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/9ead352ec38b47aeaa3ebe97f766847e.png
[fd64a2ffe7024a859491b4f330e85ecb.png]: /images/20220828/9e30e99087744ef1bffeb225c01220dd.png
[76cc50965b4c49aead4bf31c8f856239.png]: /images/20220828/da53d7bb5e21486aa9a9948018e237fe.png
[8af75c844e524313a4016260a9a844f3.png]: /images/20220828/72f8473b18b4480ca0f4974aedd33916.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/80d132d087374534b7c5668e130f19ef.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/f142cb8b52754f0aabc27c74544c2987.png
[485af9639c1246c6a599b680509a85c9.png]: /images/20220828/757aed02115f4832bfb22cb599ba0bbd.png
[a78b6f94dc3f4923ac2fa9090cca9151.png]: /images/20220828/5d31663750cf45b58bf06f89edde95a6.png
[b030e6089bf64b3d8d609a158e86b972.png]: /images/20220828/831420ace2024b95a8c877f92d8a035a.png
[9e384a5dbee04288a5478703d81aae86.png]: /images/20220828/9402bd6efe2e409d959fbd6ba62971ae.png
[03ef762ec407422bb92de19578d075fc.png]: /images/20220828/14d057a98ccd46ac88712cf3c1c37d0f.png
[e5781296db8742a8ae7c8b244ac61698.png]: /images/20220828/bbd102eb174247698bb4b27147838e13.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/4b22deb385fd4b72993d5465189fce9d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/8f9f745dd7784bb7ba698e2f2e0a3300.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/2e46f1f0da8046cf8fe8c2964ccf1de2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/007eedafb23c4967bcc31b2b02d421be.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/d5e81ef3763f4c86bdabf94f341bd540.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/489537beb9184daaac9e1ab999ccfec4.png