刷刷刷Day4|面试题 02.07. 链表相交

面试题 02.07. 链表相交

LeetCode题目要求

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

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

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解题思路

根据题目要求分析，如果存在交点，那么说明从交点开始链表A和链表B的长度是相等，
因此我们可以以短的链表为基准，让长链表先步进，
直到长链表剩余长度与短链表一致后再一起遍历，并进行比较，出现相等时即返回找到交点

如上图所示，两个链表的长度相差1，他们的相交点为 8，那么后续的长度肯定是一致的。所以我们变换为比较两个相等长度的链表，且出现相同节点时即找到交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 4 1 8 4 5
        // 5 0 1 8 4 5
        // 根据题目要求分析，如果存在交点，那么说明从交点开始链表A和链表B的长度是相等，
        // 因此我们可以以短的链表为基准，让长链表先步进，
        // 直到长链表剩余长度与短链表一致后再一起遍历，并进行比较，出现相等时即返回找到交点

        // 计算链表长度
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;

        while (curA != null) {
            curA = curA.next;
            lenA++;
        }
        while (curB != null) {
            curB = curB.next;
            lenB++;   
        }

        curA = headA;
        curB = headB;
        // 比较链表长度, 交换 A B 位置
        if (lenA < lenB) {
            int tmp = lenA;
            lenA = lenB;
            lenB = tmp;

            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }

        // 两个链表长度相减，通过上面的处理，始终将 A 链表作为长的
        int gap = lenA - lenB;
        // 根据长度差，遍历链表 A，步进到剩余长度与 B 相等
        while (gap-- > 0) {
            curA = curA.next;
        }

        // 遍历两个链表，剩余长度已经是一致的了
        while (curA != null) {
            // 如果两个节点相等， 说明是相交位置
            if (curA == curB) {
                return curA;
            } else {
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    }
}

重难点

重点理解相交点后的链表结构及长度
附：学习资料链接