力扣---LeetCode160. 相交链表(代码详解+流程图)-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣---LeetCode160. 相交链表(代码详解+流程图)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

“风格相同的人总会相遇千万个人中万幸得以相逢.”
本章的内容是力扣每日随机一题的部分方法的解析

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
力扣---LeetCode160. 相交链表(代码详解+流程图)

链接：

160. 相交链表 link

思路：

根据题目这是两个问题先判断是否相交在找到两个链表相交的起始节点。

判断是否相交

尾节点是否相等相等尾节点相等就相交(不是比较值而是地址)
例如下图A B链表尾节点值相等但是不相交
力扣---LeetCode160. 相交链表(代码详解+流程图)

寻找相交起始节点

A链表所有节点跟B链表都比较一遍，相等的那个就是交点
分别求两个链表的长度countA和countB，长的先走差距步|countA-countB|步再同时走，第一个相等的就是相交

方法一：暴力求解法

1.1 时间复杂度：O(M*N)

1.2 代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *tailA=headA;
    struct ListNode *tailB=headB;
    while(tailA)
    {
        tailB=headB;
        while(tailB)
        {
            if(tailA!=tailB)
            {
                tailB=tailB->next;
            }
            else
            {
                return tailA;
            }
        }
        tailA=tailA->next;
    }
    return NULL;
}

方法二：双指针

2.1 时间复杂度：O(N)

2.2 代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *tailA=headA;
    struct ListNode *tailB=headB;
    int countA=1;
    int countB=1;
    while(tailA->next)
    {
        tailA=tailA->next;
        countA++;
    }
    while(tailB->next)
    {
        tailB=tailB->next;
        countB++;
    }
    if(tailA!=tailB)
    {
        return NULL;
    }
    //这里也可以使用三目操作符
    int gap=abs(countA-countB);
    struct ListNode *longlist=headA;
    struct ListNode *shortlist=headB;
    if(countA<countB)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}