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

一时失言乱红尘 2024-03-29 14:22 36阅读 0赞

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

如下面的两个链表：

![824defb1aa1ffafff732355117d10e00.png][]

在节点 c1 开始相交。

示例 1：

![dc5be543f0094be208bd995a79bdb2b8.png][]

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

![cd4ef6ab21306ab9d5add620a13657d9.png][]

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

![875d4cd901ef45d131b1758e9b255a18.png][]

输入：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) 内存。  
本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

**方法1.哈希集合**

因为hashset的特点是不会有重复元素，可以先遍历将其中一个链表中的元素放进hashset中，然后再将另一个链表的元素遍历，并与hashset中的元素进行比较看是否有相同的元素，当第一个出现相同的就可以直接返回当前节点，否则返回null。（要注意当元素过大的时候添加进hashset会出现“哈希冲突”，即有不同对象有相同的hashcode）。

class Solution {
        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            HashSet<ListNode> set = new HashSet<ListNode>();
            ListNode temp = headA;
            while(temp!=null){
                set.add(temp);
                temp=temp.next;
            }
            temp=headB;
            while(temp!=null){
                if(set.contains(temp)){
                    return temp;
                }
                temp=temp.next;
            }
            return null;
        }
    }

**方法二：双指针法**

用了方法一的话可能会有读者会思考例1中的例子为什么A的1和B的1相同但不是交点。这题实际上求的是地址和值都相同的点，而A和B是链表不是数组，数字相等并不等于地址相同，A的1和B的1是内容相同但地址不相同所以并不是相同交点。所以这里用双指针的方法比较容易明白。

假设链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b个节点，两个链表相交的部分有 c 个节点，则有 a+c=m ，b+c=n。

当链表headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

1.每步操作需要同时更新指针pA 和 pB。

2.如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。

3.如果指针 pA 为空，则将指针pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。

4.当指针 pA 和pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

即当a!=b时，假设a>b，那么a会比b先到null，那么就回到B链表的头结点继续往前，如果有交点的话最终他们的走过的路会分别是a+c+b，b+c+a，即相遇。

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode pA = headA, pB = headB;
            while (pA != pB) {
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
        }
    }

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

[824defb1aa1ffafff732355117d10e00.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/a56b84e8b61a43f2ac10b8e944a2c5dc.png
[dc5be543f0094be208bd995a79bdb2b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7eb9b07faac54f7b8f7bd65f6636d9ef.png
[cd4ef6ab21306ab9d5add620a13657d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/5cd403006e57498d968fec73885fc7ed.png
[875d4cd901ef45d131b1758e9b255a18.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/98bab0a0e4a04ff1961861899adc5319.png