相交链表（数据结构）

160. 相交链表 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

题目

解决思路

1，找到相交的点

相交链表的关键也就是找到相交的点，所以我们需要首先判断有没有相交的节点，没有相交的节点结束返回NULL，有相交的节点继续，此时我们已经算出各自的链表的长度（一次循环）

2，算出长度差值

3，遍历找到节点

最后一步两个节点同时移动，当两个节点的地址等于的时候，此时也就是找到了相交的节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    //这里的起始节点是1，因为链表场赌博是从1开始计算的
    int contA = 1;
    int contB = 1;
 
    //进行判断，是不是有相同的尾结点
    ListNode*cureA = headA;
    ListNode*cureB = headB;
    while(cureA)
    {
        cureA = cureA->next;
        //计算A链表的长度
        contA++;
    }
    while(cureB)
    {
        cureB = cureB->next;
        //计算B链表的长度
        contB++;
    }
    if(cureA != cureB)
    {
        return NULL;
    }
 
    //假设法，假设A长
    //长的先走，直到指向的位置是平行的
    if(contA > contB)
    {
        int contsame = contA-contB;
        while(contsame--)
        {
            headA = headA->next;
        }
    }
    else
    {
        int contsame = contB-contA;
        while(contsame--)
        {
            headB = headB->next;
        }
    }
 
    //找到交点
    while(headA)
    {
        if(headA == headB)
        {
            return headA;
        }
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}