[数据结构与算法]【LeetCode系列】160. 相交链表

??前面的话??

大家好！本篇文章将介绍关于数据结构之链表的OJ题，来自力扣：160. 相交链表 题解，展示代码语言暂时为：Java语言。（后续会更新C++代码）

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏??留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2021年11月29日🌴
??坚持和努力一定能换来诗与远方！
💭刷题推荐书籍：📚《剑指offer专项版》，📚《剑指offer第2版》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🙏作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

??160. 相交链表 ??

🔐题目详情

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

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 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 。

提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

💡解题思路

对于相交链表这道题，可以采取双指针方法解决，我们来观察一下相交链表，交点前半部分不相同，交点后半部分是一样的，我们可以遍历两个链表，但是需要想办法让遍历链表的两个指针同时走到交点处，具体方法看以下步骤：
第一步，定义双指针，求出两个链表的长度，根据链表长度调节指针，让其中一个指针永远指向长的链表中结点，假设指向长链表结点指针为$pl$,指向短链表结点指针为$ps$。
第二步，根据两链表长度之差$len$，让$pl$先走$len$步，然后让两指针同时前进，这样如果存在交点，就能同时遍历到相交结点处。
第三步，让$pl$与$ps$同时遍历链表，得到两指针指向同一地址的结点（相交结点）或者两指针（引用）同时指向null（表示无相交结点）。

时间复杂度：O（N）
空间复杂度：O（1）

🔑源代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //pl永远指向长的链表
        ListNode pl = headA;
        ListNode ps = headB;
        int linkLen1 = 0;
        int linkLen2 = 0;
        while (pl != null) {
            linkLen1++;
            pl = pl.next;
        }
        //不要忘记将pl重新指向头
        pl = headA;
        while (ps != null) {
            linkLen2++;
            ps = ps.next;
        }
        ps = headB;

        //计算链表长度差值
        int len = linkLen1 - linkLen2;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = linkLen2 - linkLen1;
        }
        //让长的链表先走差值步
        for (int i = 0; i < len; i++) {
            pl = pl.next;
        }
        //同时走,链表引用相等时表示链表相交于一节点，或都走到null了
        while (ps != pl) {
            pl = pl.next;
            ps = ps.next;
        }
        //返回节点地址，如果走到空返回null（如果链表不相交，最终两个引用都为空）
        return pl;
    }
}

🌱总结

找相交结点的难点是如何使两指针同时指向相交的结点，这个时候我们要根据两链表的长度和相交链表的特点设计出让长链表指针先走差值步的方法，使两指针能够同时走到相交结点的位置。