目录

前言

 一，思路

1）暴力

2)同步指针

二，代码实现

---

前言

   依旧是力扣上的一道题，有许多新思路提供给我们

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

      我们先来分析题干，相交链表这个相交值得我们去思考一下，我们平常惯性思维的相交都是X型的，要注意单链表的相交并不是简单的X型相交，而是如图所示的Y字型相交，因为我们知道单链表的节点里存储数据和 next 指针，当两个链表的某一个节点的next指针都指向同一个节点时，两链表相交，但无论如何一个节点只能存储一个next指针，所以交汇之后只能形成Y字型的相交。

    题目要求大致总结以下两点：

1. 判断是否相交
2. 若相交，找出第一个交点

 一，思路

     我们之前做过的一道题讲了一个链表很好用的思路叫逆置，但在这道题中，假设我们逆置来做，则无法使c1节点有俩next指针，所以这个方法哒咩

     对于第一个要求，我们可以判断尾指针，注意用地址判断

1）暴力

     给两个指针将两个链表的节点都比较一遍，找出相同的节点的即为所求     

     但时间复杂度会高很多O(N^2)

2)同步指针

     先找出两个链表同时的节点，例如找出短链表的头节点对应的长链表的节点 a1和b2，两个指针从这开始遍历无需一一比对节点是否相同

二，代码实现

/**
 * 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){
        curA = curA->next;
        ++lenA;
    }
    while(curB->next){
        curB = curB->next;
        ++lenB;
    }
    //尾节点不相等就是不相交
    if(curA !=  curB){
        return NULL;
    }

    //长节点先走差距步，再同时走，第一个像等的就是交点
    //假设法
    int gap = abs(lenA - lenB);
    struct ListNode *longList = headA, *shortList = headB;
    if(lenB > lenA){
        longList = headB;
        shortList = headA;
    }

    while(gap--){
        longList = longList->next;
    }

    while(longList != shortList){
        longList = longList->next;
        shortList = shortList->next;
    }
    return shortList;
}

 因为无需一一比对，所以空间复杂度为O(N)