【LeetCode刷题日记】160：相交链表

题目背景：LeetCode160

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 示例 1：

示例 2：

示例 3：

题目答案：

(版本一)先行移动长链表实现同步移动
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

}

题目解析：

在拿到这题目的时候，我们需要区分的第一个概念就是，我们要找的相交的节点，需要比较的是地址值，而不仅仅是节点的val值 简单的来说，如果两个节点的地址值相等，就已经保证了节点val值相等，同时还能保证相交节点之后的节点都是一样的，因为一个节点只能指向一个next，不存在在节点之后分叉的情况（前提是相交链表）。 因为这些的前提就是两个链表有相交节点，有相交节点的前提就是两个节点的地址值相等，两个节点的地址值相等就已经保证了在第一个相交节点之后，两个链表的之后节点也是完全相等的，也就是共用一条链的感觉。如图相交节点是2，2后面的节点是两条链都有的，因此2节点处的地址值才相等。

所以，仅仅比较节点的val值完全是片面的，要找到地址值相等的节点才可以。 因此，我们这题的主要思路就是先找到相交节点： 如果是一长一短的链表，我们先让长链表的指针移动两个链表的长度差的值，让两个链表从同一起点开始，因为我们要找的相交节点，要求可以说是很苛刻，相交节点之后的长度，val值等等，都要完全一样，不然就不是相交节点。所以我们还要记录两个链表的长度，从而进行比较和计算长度差。

同一起点之后： 我们就开始比较两个链表的指针，去寻找相交节点，如果不相同，则同时向后移动，继续比较，这里强调是同时相同，因为要保证相交节点之后两个链表的长度也是一样的，因为已经是从同一起点开始移动比较了。 如果没找到，则两个链表不相交，循环退出，返回空指针。 我们这里curA==curB，比较的就是地址值，仅仅比较val值太片面，不能保证之后的节点是否相等，这是本题的核心。

易错点： 我们在题目中先定义ListNode curA curB的时候，这是定义加初始化，但是由于我们用这两个指针进行了循环计算长度，此时指针位置已经移动到末尾了，所以我们为了方便下面的使用，又进行了操作 curA=headA，curB=headB，这里是重置，归位的作用。 同时我们还要比较哪个链表的长度长，哪个短，需要进行条件判断，比较麻烦，我们在这里有一个操作，直接进行硬性规定，直接令curA为长链表的表头，lenA为其长度。只需要进行一个判断，如果B>A，直接进行交换即可，需要定义一个 临时变量进行临时存储。

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励，有疑问也可以在评论区发出来，让我们一起进步！