leetcode：交叉链表

题目描述

题目链接：160. 相交链表 - 力扣（LeetCode）

题目分析

我们先要搞清楚一个概念，单链表可以相交，但绝对不会交叉

原因如下：

单链表中，多个结点可以存一个结点的地址，但是一个结点不可能存多个结点的地址

因为每个结点只有一个next

所以链表的相交一定是Y字形的

这里我们要做的有两步：

• 判断是否相交
• 找交点

思路一

暴力求解：A链表的所有结点依次去B链表找一遍

注意：一定要用结点的地址去比对

思路二

判断相交：

分别找尾结点，尾结点地址相同就相交

找交点：

算出两个链表的长度，得出两个链表的长度差，让长链表先走差距步，然后同时走，当第一个地址相同的时候，这就是交点

这个算法的时间复杂度是F(3N)，即O(N)

完整算法：

我们先定义curA，curB分别指向两个链表，用while循环求长度，并判断是否相交（只有相交了才会有交点）如果不相交则返回NULL，相交再进行下一步

我们得到lenA和lenB，用C语言自带的函数abs求出差距的绝对值

int n=abs(lenA-lenB);

那么谁先走呢，我们用假设法：假设A长B短

如果假设错误，那就纠正过来

让长的先走差距步

然后同时走，想等的时候返回任意一个地址就是交点

代码示例

根据思路二，我们写出代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *curA=headA,* curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB=curB->next;
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int n=abs(lenA-lenB);
    struct ListNode *longList=headA, *shortList=headB;
    if(lenB>lenA)
    {
        longList=headB;
        shortList=headA;
    }
    while(n--)
    {
        longList=longList->next;
    }
    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }
    return longList;
}

结果就可以通过了