力扣-160题相交链表（C++）- 判别两个链表是否有共同节点（新思路）

喜欢ヅ旅行 2022-08-31 00:50 23阅读 0赞

题目链接：[https://leetcode-cn.com/problems/intersection-of-two-linked-lists/][https_leetcode-cn.com_problems_intersection-of-two-linked-lists]  
题目如下：  
![在这里插入图片描述][d60f84736025ef7b41c1fe40c711825c.png]  
![在这里插入图片描述][d9d7abcf07638cdc6a2aa42ee46cd926.png]  
![在这里插入图片描述][235a834e42ddc0e8fe5b42d4a46b0304.png]

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
            //时间复杂度：O(m+n)
            //空间复杂度：O(1)
            //思路：如下草稿所示
    
            ListNode* p1=headA;
            ListNode* p2=headB;
    
            bool flag1=true;
            bool flag2=true;
    
            while(p1&&p2){
        
                if(p1==p2) return p1;
                else{
        
                    p1=p1->next;
                    p2=p2->next;
                }
    
                if(p1==NULL&&flag1==true){
        
                    p1=headB;
                    flag1=false;
                }
                
                if(p2==NULL&&flag2==true){
        
                    p2=headA;
                    flag2=false;
                }
            }        
    
            return NULL;
        }
    };

![在这里插入图片描述][b3876c606ae0af452c62cd3811cf3af8.png]

[https_leetcode-cn.com_problems_intersection-of-two-linked-lists]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[d60f84736025ef7b41c1fe40c711825c.png]: /images/20220829/17295e51d26c4184aeb8f1e307cd53e4.png
[d9d7abcf07638cdc6a2aa42ee46cd926.png]: /images/20220829/bd4cfd8ceead417787499073b1b422eb.png
[235a834e42ddc0e8fe5b42d4a46b0304.png]: /images/20220829/5be755c782364a5da30122f76af3c602.png
[b3876c606ae0af452c62cd3811cf3af8.png]: /images/20220829/5a606d6c0e8c4ddc9a8e8e478b17adb8.png