力扣OJ题——相交链表

题目：160. 相交链表

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

思路一（暴力求解）：

A链表的每个节点依次跟B链表中节点进行比较，如果有相等就是相交，第一个相等就是交点

接下来我们看一下思路一的时间复杂度吧~

因为我们这里不知道这两个链表之间的大小关系，

所以时间复杂度可以是O（N^2）或者O（N*M）

思路二：

1.先找尾节点，尾节点的地址相同就相交，不相同直接返回NULL

2.接下来要处理的就是判断相交链表的第一个节点，我们先计算两个链表的长度，让长的链表先走完长度差，再同时找交点，第一个地址相同的就是交点

接下来我们看一下思路二的时间复杂度

这里算了一下是3N，所以时间复杂度就应该是O（N），显然要优于思路一

所以接下来我们来实现一下思路二~

首先第一步：先找尾节点，尾节点的地址相同就相交，不相同直接返回NULL

代码如下：

    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
   
    while(curA->next)
     {
        curA = curA->next;
    }
    
    while(curB->next) 
    {
        curB = curB->next;
    }


    if(curA!=curB)  return NULL;//尾节点不相等，说明不相交，直接返回NULL

接下来第二步：

a.分别算出两个链表的长度，进而算出二者的长度差值

b.让长的链表先走完长度差

c.  两个链表同时走，直到遇到相同的节点

代码如下：

    curA = headA;
    curB = headB;
    int lenA = 0, lenB = 0;//分别算出两个链表的长度
    while(curA)
     {
        lenA++;
        curA = curA->next;
    }
    
    while(curB) 
    {
        lenB++;
        curB = curB->next;
    }
    
    int len = abs(lenA-lenB);//len为二者的长度差

    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;

    if(lenB>lenA)
     {
        longList = headB;
        shortList = headA;
    }

    //让长的链表先走完长度差
    while(len!=0)
    {
        longList = longList->next;
        len--;
    }
    
    //两个链表同时走，直到遇到相同的节点
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;

将上面两步的代码结合起来，这道题就过了

当然，我们也可以将这个代码写得更简略一些：比如将计算长度的代码融入第一步的遍历

这里因为要逻辑更清晰一些才将它们分开的，不过这些也都是小问题而已啦

好啦，到此为止，今天的相交链表问题就结束啦，如果文中分析，题解代码有不足的地方欢迎大家在评论区讨论和指正

让我们在接下来的时间里一起学习，一起进步吧~