【160. 相交链表】

---

一、题目描述

题目链接

---

二、题目思路

思路一：暴力求解-穷举
依次取A链表中的每个节点跟B链表中的所有节点比较，如果有地址相同的节点，就是交点
时间复杂度O(N^2)
思路二：
1.尾节点相同就是相交，否则就不相交
2.求交点：长的链表先走（长度差）步，再同时走，第一个相同的就是交点
时间复杂度O(N)

---

三、题目代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    struct ListNode * listA = headA;
    struct ListNode * listB = headB;
    int lenA=1;int lenB=1;
    while(listA->next)
    {
    
        listA=listA->next;
        lenA++;
    }
    while(listB->next)
    {
    
        listB=listB->next;
        lenB++;
    }
    if(listA != listB)
    {
    
        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 shortlist;
}

---

以上是本篇文章的全部内容，如果文章有错误或者有看不懂的地方，多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助，可以给喵博主一个关注，你们的支持是我最大的动力。