链表相交与链表求环

刺骨的言语ヽ痛彻心扉 2022-04-24 07:14 240阅读 0赞

## 链表相交与求环 ##

初看链表相交与链表求环，我还懵的，什么是链表相交？链表还能相交，什么是链表求环，链表还能求环，哈哈，直到看到这个。。。。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]  
链表中有环  
![在这里插入图片描述][20190418132123457.png]  
看到这个图我才发现链表还可以这么玩，涨知识了。。不过同时看到这道题之后，也是勾起了浓厚的兴趣，那么我们到底该如何判断链表相交与链表求环呢

**- 首先我们来说一下链表相交的问题**  
开始看到这个问题的时候我也挺懵的，不知道如何去解决这个问题，不过只要你多看一会图其实就知道如何去解决了。  
**1>** 采用双指针解决问题\*\*：如果链表会相交，那就说明肯定在某个节点就重合了，那么我们只需要找到这个节点即可。但是我们也不知链表的具体样子是什么样的，有可能一样长，有可能一长一短，如果我们要比较的话，就得让链表一样长然后同时遍历比较。那么问题来了，如何让两个链表一样长呢，这就简单了，我们分别计算两个链表的长度，让让长的链表指针先走几步，然后两个指针同时走不就行了，最后不就能得出结果了。下面我来说一下具体得方法。  
(1) 分别计算两个链表的长度，计算差值  
(2) 让长链表的指针先走差值步。  
(3) 然后两个链表同时遍历比较即可

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            int lenA = 0;
            int lenB = 0;
            ListNode* p = headA;
            ListNode* q = headB;
            while(p) {
                ++lenA;
                p = p->next;
            }
            while(q) {
                ++lenB;
                q = q->next;
            }
            
            // 尾结点不一样，直接返回空。
            if (p != q) return nullptr;
            
            int diff = lenB - lenA;
            // 1. p 指向较长的那个链表的头。q 指向较短的那个。
            if (diff > 0) {
                p = headB;
                q = headA;
            } else {
                p = headA;
                q = headB;
                diff = -diff;
            }
            while(diff--) {
                p = p->next;
            }
            
            // 2. p 和 q 一起向前走
            while(p != q) {
                p = p->next;
                q = q->next;
            }
            return p;
        }

**链表求环问题**  
乍一看，挺高大上的，一时之间我似乎还没有思路，其实并不是很难，只是我们想的太复杂了。  
**2>采用快慢指针解决问题**：所谓快慢指针并没有那么复杂，其实这就和我们小学遇到的数学题一样的，两个人同时在操场跑圈，一个跑的快，一个跑的慢，问快的最少花多长时间就能将慢的那个人追上。采取这个思路，就容易多了，如果一个链表中有环，如上图那种形式，那么我们让快指针一次走两步，慢指针一次走一步，两个人同时出发，如果链表中有环路，终有某一时刻，我们的快指针将慢指针追上，否则就是没有环路。下面我们来看具体实现。

bool hasCycle(ListNode *head) {
          if(head==NULL){
              return NULL;
          }
            ListNode* fast=head;
            ListNode* slow=head;
            while(fast!=NULL&&fast->next!=NULL){
                fast=fast->next;
                slow=slow->next;
                fast=fast->next;
                if(fast==slow){
                    return true;
                }
            }
            return false;
        }

以上就是关于链表相交于链表环路的问题，其实也并没有多复杂，自我感觉啊，有时候我们不会解决，没有思路，并不是因为题过于难，而是我们想的过于复杂了，往简单想想也许就会豁然开朗。。。。 来自一个萌萌哒的分享。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220218/3751b0eba6d244c4a87bf3e4eb578354.png
[20190418132123457.png]: /images/20220218/bdb1bb3f552e4c6d8b580af83079970f.png