相交链表问题-你真的懂了吗?

题目要求

链接：160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

注意：相交链表是Y形状的，不是X形状的。一个结点只有一个next指向

如何判断相交：

方法：比较两个链表的尾结点地址是否一致

相交和不相交的不同之处

相交：两个链表从相交结点开始，后面的结点的地址一致==>尾结点相同

不相交：两个链表的所有结点的地址都是不相同的

所以只需要遍历两个链表，找到两个链表的尾结点，然后比较是否相等。如果相等则进行下一步，找相交起始节点。如果不相等 -> 直接返回NULL

//找两个链表的尾
while(tailA->next != NULL)
{}
while(tailB->next != NULL)
{}
//判断是否相等
if(tailA != tailB)
{
    return false;
}

如果相交，如何找到相交起始结点

错误思路：

同时遍历两个链表，比较对应结点的地址是否一致

不可行原因：

两个链表的长度不一样，如果二者在相交结点前的长度一致，则可以这样比较(==这也是后面思路2的想法==)

若相交结点前，两个链表的长度不一致，则不可行！

思路1：

若两个链表相交，则它们至少有一个结点的地址相同(从相交起始结点向后，结点的地址都相同)

• A链表中的每个结点分别和B链表中的所有结点进行地址比较

  • 用cur遍历A链表，B链表每次进入循环都从头开始遍历

  • 如果结点地址相同，该结点就是开相交结点，返回该位置即可

  • 如果不相同，继续比较。

• 循环结束条件：A链表的所有结点都比较结束，即cur为NULL跳出循环。比较完了都没有返回->说明不相交

当然，也可以用B链表的每个结点分别和A链表中的所有结点进行地址比较

时间复杂度分析：假设A链表有M个结点，B链表有N个结点

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

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //如果其中一个链表为空，不可能存在相交
    if(headA  == NULL|| headB == NULL)
    {
        return NULL;

    //A中的每个结点和B分别比较(B和A比较也可以)，看二者的地址是否一致 
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    while(curA)
    {
        //A链表的每个结点和整条B链表进行比较
        curB = headB;
        while(curB)
        {
            //地址比较
            if(curA == curB)
            {
                return curA;
            }
            //curB向后移动
            curB = curB ->next;
        }
        //A的下一结点继续比较
        curA = curA->next;
    }
    //A的结点都比较完了，说明找不到
    return NULL;
}

思路2：

• 上面判断相交得过程，可以分别把两个链表的长度也求出来，记为lenA和lenB

  • 注意：标志二者长度的变量要初始化为1(因为如果只有一个结点，是不会进入循环的)

• 求出两个链表的长度差记为gap， 由于不知道是lenA大还是lenB更大，所以可以使用求绝对值的函数abs求出gap

• 长链表先走gap步，然后二者再一起走，比较二者的结点的地址是否一致，第一个地址相同的结点就是相交结点

  • 可以先假设一个链表是长链表,另一个是短链表。然后再根据长度判断假设是否合理

图解：

注意：短链表和长链表可能是一条链

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //其中一个链表为空->不相交
    if(headA == NULL|| headB == NULL)
    {
        return NULL;
    }

    //如果相交：尾结点相同
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1;//不能初始化为0,如果只有一个结点，不进入循环
    int lenB = 1;//和上面同理

    //遍历找两个链表的尾,顺便求两个链表的长度
    while(tailA->next !=NULL)
    {
        lenA +=1;
        tailA = tailA->next;
    }
     while(tailB->next !=NULL)
    {
        lenB +=1;
        tailB = tailB->next;
    }

    //判断尾结点是否一致,不一致则不相交
    if(tailA != tailB)
    {
        return NULL;
    }
    //计算出两个链表长度的差值为gap
    int gap = abs(lenA - lenB);//未知谁大，所以求绝对值
    //长链表先走gap步，二者再一起走找交点
    //假设一个链表长
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    //判断假设是否成立：
    //lenA < lenB 说明假设不成立，B链表更长
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    //长链表先走gap步
    while(gap--)
    {
        longList = longList -> next;
    }
    //二者再同时走,二者相等就是相交点
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    //当longList == shortList时跳出循环，此时二者指向的就是起始相交结点

    //如果是不相交的，上面就尾结点不同就已经返回了
    //代码能到指向这说明两个链表就是相交的
    return shortList;
}