剑指 Offer 52. 两个链表的第一个公共节点

亦凉 2022-11-22 00:04 112阅读 0赞

# 题目 #

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：  
![在这里插入图片描述][20201102205737962.png_pic_center]  
在节点 c1 开始相交。

示例 1：  
![在这里插入图片描述][20201102205756502.png_pic_center]

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

示例 2：  
![在这里插入图片描述][2020110220590645.png_pic_center]

> 输入：intersectVal = 2, listA = \[0,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1  
> 输出：Reference of the node with value = 2  
> 输入解释：相交节点的值为 2（注意，如果两个列表相交则不能为 0）。  
> 从各自的表头开始算起，链表 A 为 \[0,9,1,2,4\]，链表 B 为 \[3,2,4\]。在 A  
> 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：  
![在这里插入图片描述][20201102210001179.png_pic_center]

> 输入：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。

注意：

*  如果两个链表没有交点，返回 null.
 *  在返回结果后，两个链表仍须保持原有的结构。
 *  可假定整个链表结构中没有循环。
 *  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof][https_leetcode-cn.com_problems_liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof]

# 解题思路 #

假设两个链表公共部分长度为C,两个链表的长度为L1 + C和L2 + C

*  定义两个指针temp1 = headA和temp2 = headB,同时前进
 *  当temp1 == null时,把temp1 = headB,再走一遍链表B
 *  当temp2 == null时,把temp2 = headA,再走一遍链表A
 *  当AB有公共节点的时候,temp1和temp2同时指向公共节点
 *  当AB没有公共节点的时候,temp1和temp2同时为null

证明如下:

L1 + C + L2 = L2 + C + L1
    L1 + L2 = L2 + L1

# 代码 #

/** * 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) { 
            // 定义两个指针
            ListNode temp1 = headA;
            ListNode temp2 = headB;
            // 两个指针不相等时,循环
            while (temp1 != temp2) { 
                // temp1不断前进,为null时,重新指向headB
                temp1 = temp1 == null ? headB : temp1.next;
                // temp2不断前进,为null时,重新指向headA
                temp2 = temp2 == null ? headA : temp2.next;
            }
            // 有公共节点的时候,temp1和temp2指向公共节点
            // 没有公共节点的时候,temp1和temp2同时指向null
            return temp1;
        }
    }

# 复杂度 #

*  时间复杂度:O(m + n),mn分别为两个链表的长度
 *  空间复杂度:O(1),指针占用常量级额外空间

[20201102205737962.png_pic_center]: /images/20221120/21fc520c4bae49f886886ffdb72c0aed.png
[20201102205756502.png_pic_center]: https://img-blog.csdnimg.cn/20201102205756502.png#pic_center
[2020110220590645.png_pic_center]: https://img-blog.csdnimg.cn/2020110220590645.png#pic_center
[20201102210001179.png_pic_center]: https://img-blog.csdnimg.cn/20201102210001179.png#pic_center
[https_leetcode-cn.com_problems_liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof]: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof