力扣---LeetCode160. 相交链表(代码详解+流程图)_leecode 相交链表

---

前言

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

---

160. 相交链表

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

链接：

160. 相交链表 link

思路：

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

• 判断是否相交

尾节点是否相等相等尾节点相等就相交(不是比较值而是地址)
例如下图A B链表尾节点值相等但是不相交

• 寻找相交起始节点

1. A链表所有节点跟B链表都比较一遍，相等的那个就是交点
2. 分别求两个链表的长度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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：双指针

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2. 3流程图：

注意：

这种链表是不可以逆置的，因为c1这个节点只有一个next所以不可能有两个next同时指向a2和b3(error)

补充一个知识点：

abs 函数是存在于多种编程语言（包括且不限于：C语言、C++、Fortran、Matlab、Pascal、Delphi、Visual Basic 和 VBA）中的一种用于求数据绝对值的函数。

---

总结

Ending,今天的力扣每日一题内容就到此结束啦，如果后续想了解更多，就请关注我吧，一键三连，还有许多种方法没有写出希望各位佬补充哦~