LeetCode 160.相交链表

2023-09-08 46

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode 160.相交链表

💡题目分析

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

💡解题思路

🚩步骤一：找尾节点

struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1,lenB = 1;
    while(tailA)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB)
    {
        tailB = tailB->next;
        lenB++;
    }

🚩步骤二：判断尾节点是否相等

判断尾节点是否相等，如果尾节点相等就是相交

if (tailA != tailB)
{
    return NULL;
}

🚩步骤三：找交点

🍄思路1

A链表所有节点跟B链表都比较一遍，相等的那个就是交点

这种暴力求解法解决这道题是没问题的。但是这种解法时间复杂度为 O(N^2) / O(N*M)，要求优化到 O(N)，所以我们不采用这种暴力解法，建议使用下一种解法👇

🍄思路2

分别定义两个链表的长度 lenA 和 lenB，长的先走abs(lenA - lenB)步（差距步），然后再同时走，第一个相等的就是相交节点

//长的先走差距步
    int gap = abs(lenA - lenB); //abs函数是对整数进行取绝对值
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }

👇图解👇

此方法整体时间复杂度为：O(M+N) / O(N)，空间复杂度为：O(1)

🔔接口源码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1,lenB = 1;
    while(tailA)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB)
    {
        tailB = tailB->next;
        lenB++;
    }
    //判断最后一个节点是否相等（是否相交）
    if(tailA != tailB)
    {
        return NULL;
    }
    //长的先走差距步
    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    //一一对应比较，判断重叠节点(因为前面已经经过是否相交的判断，所以执行至此，必定是相交的)
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    //二者相等，任意一一个都是相交起始点
    return longList;
}