详解LeetCode160：相交链表--C语言实现

• 题目要求
• 解题思路
• 代码实现

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 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 个节点。

示例 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 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

首先，我们要判断两个链表是否相交，若相交，则求交点。我们可以清楚的知道，任意一条链表为空，两条链表都不相交，此时返回NULL。那么，除去这种情况，我们该怎么判断两条链表是否相交呢？我们要知道链表的相交不是我们日常理解的这种相交方式：

本题的链表相交到相交点之后就只有一条链表，即以下这种形式：

所以，我们先分别求出两条链表的长度lenA和lenB，此时我们所使用的两个指针都走到了两条链表的尾节点处，此时判断两个指针所指向的尾节点是否相同，若相同则说明一定有相交点，若不相同，说明两个链表不相交，返回NULL。

当尾节点判断相同时，我们就得到了链表相交这一重要信息，紧接着，我们之前求的链表长度就起作用了。我们可以用让lenA减去lenB，取结果的绝对值k，即两条链表的差距长度。然后让指向长链表头节点的指针先移动差距长度k步。

以上文的示例1为例：

A链表和B链表长度相差1，让指向B链表头节点的指针先移动差距长度1步。此时指针指向b2，这时候指向A链表头结点的指针指向a1，然后让两者同时移动，每次移动都判断两者指向的节点是否相同，第一次相同的即为相交节点，返回该节点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //有一个为空，就直接返回空
    if(headA == NULL || headB == NULL)
    {
        return NULL;
    }
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int sizeA = 0;
    int sizeB = 0;
    //求两条链表的长度
    while(curA->next)
    {
        ++sizeA;
        curA = curA->next;
    }
    while(curB->next)
    {
        ++sizeB;
        curB = curB->next;
    }
	//两个循环走完，curA和curB都走到了链表的尾节点
    if(curA != curB)//尾节点不同，说明不相交，直接返回NULL
    {
        return NULL;
    }

    //尾节点相同，说明一定相交
    int k = abs(sizeA - sizeB);
    curA = headA;
    curB = headB;

    //长链表先走差距步
    while(k--)
    {
        if(sizeA > sizeB)
        {
            curA = curA->next;
        }
        else
        {
            curB = curB->next;
        }
    }
    //判断所指向的jie'dian'shi
    while(curA && curB)
    {
        if(curA == curB)
        {
            return curA;
        }
        curA = curA->next;
        curB = curB->next;
    }
    return NULL;
}

如有问题，希望大家指出！同时，若大家有更好的思路和建议也请指正！