双指针-链表相交

发布时间:2024年01月24日

1.题目描述

题目链接
在这里插入图片描述
解题思路:题目求两个链表是否有交点,一般思路就是一个一个比较,虽然可以得出结果但是时间复杂度偏高,观察可以得知两个链表如果有相交结点那么后面的每个结点都一样,因此我们可以先计算两个链表的长度,然后用一个指针遍历较长的那条链表,遍历步数为两个链表的差值,再开始比较,如果当前节点不相同,则两链表指针同时向后遍历。两指针指向相同则代表找到了相交节点。

2.测试代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len_a=0;//链表a的长度
        ListNode* p;
        p=headA;
        while(p!=nullptr){
            p=p->next;
            len_a++;
        }
        p=headA;
        int len_b=0;//链表b的长度
        ListNode* q;
        q=headB;
        while(q!=nullptr){
            q=q->next;
            len_b++;
        }
        q=headB;       
        int diff;
        // diff=len_a-len_b > 0 ? len_a-len_b : len_b-len_a;
        if(len_b>len_a){//使链表a始终为最长链表
            swap(len_a,len_b);
            swap(p,q);
        }
        diff=len_a-len_b;
        while(diff>0){//链表a先遍历差值步
            p=p->next;
            diff--;
        }
        while(p!=nullptr){
            if(p==q){
                return p;
            }else{
                p=p->next;
                q=q->next;
            }
        }
        return nullptr;
    }
};

3.测试结果

在这里插入图片描述
结果分析:通过观察题目,使用双指针使时间复杂度达到O(m+n),先用一个指针遍历较长的链表,然后两个指针同时遍历。

文章来源:https://blog.csdn.net/qq_53280985/article/details/135732349
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。