leetcode链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

 题目描述

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

示例1

  

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例2 

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

---

思路

  这道题的思路比较简单，两个链表中存在一个长链表 longlist 和一个短链表 shortlist，只需要先让longlist 走他们两个链表之间的长度差 gap，然后再遍历 longlist 剩下的节点与 shortlist 的每个节点是否有相同的，如果相同，那就返回那个节点，如果不同，那就返回NULL。

代码

 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //先计算两个链表的长度
    int sizeA = 0,sizeB = 0;
    ListNode* pcur1 = headA, *pcur2 = headB;
    while (pcur1)
    {
        ++sizeA;
        pcur1 = pcur1->next;
    }
    while (pcur2)
    {
        ++sizeB;
        pcur2 = pcur2->next;
    }
    //计算长度差
    //abs用来计算绝对值
    int gap = abs(sizeA - sizeB);
    //找长链表
    ListNode* longlist = headA;
    ListNode* shortlist = headB;
    if (sizeA < sizeB)
    {
        longlist = headB;
        shortlist = headA;
    }
    //让长链表走长度差
    while (gap--)
    {
        longlist = longlist->next;
    }
    //比较剩下节点是否相同
    while (longlist)
    {
        if (longlist == shortlist)
        {
            return longlist;
        }
        longlist = longlist->next;
        shortlist = shortlist->next;
    }

    return NULL;
}

  我们再来考虑一下特殊情况，就是 headA 或者 headB 为NULL时，此时 pcur1 或者 pcur2 就为NULL，那么 gap 就是不为NULL的链表的长度，然后长链表会走长度差，会走到NULL，所以最后一个循环也就进不去，最终就会返回NULL，所以遇到特殊情况时，不会出现对NULL指针的解引用，最后结果也是正确的。