【LeetCode 160】相交链表

谁借莪１个温暖的怀抱￠ 2022-11-28 13:36 166阅读 0赞

#### 题目描述 ####

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

![在这里插入图片描述][20200817234343911.png]

在节点 c1 开始相交。

示例 1：

![在这里插入图片描述][20200817234410254.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：

![在这里插入图片描述][20200817234520656.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：

![在这里插入图片描述][20200817234531871.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) 内存。

#### 解题思路 ####

一个比较直接直接的方法就是用双指针来解决，思路就是将链表拼成ab和ba这样就消除了两者的高度差，如果a和b有相交的部分，那么ab和ba也一定有相交的部分。具体实现步骤如下：

*  定义两个指针 pA 和 pB；
 *  pA 从链表 a 的头部开始走，走完后再从链表 b 的头部开始走；
 *  pB 从链表 b 的头部开始走，走完后再从链表 a 的头部开始走；
 *  如果存在相交的点就直接返回pA或者pB

#### 代码实现 ####

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    
    /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */
    var getIntersectionNode = function(headA, headB) { 
        let pA = headA
        let pB = headB
        while(pA !== pB){ 
            pA = pA === null ? headB : pA.next
            pB = pB === null ? headA : pB.next
        }
        return pA
    };

#### 提交结果 ####

![在这里插入图片描述][20200817234304562.png]

[20200817234343911.png]: /images/20221124/db8d5b76b7e145f2842b065e6db663b2.png?
[20200817234410254.png]: /images/20221124/e2a9222f443f45ef94098bcbcb66da9a.png?
[20200817234520656.png]: /images/20221124/d438c80b3ad146d9bdc283747c716797.png?
[20200817234531871.png]: /images/20221124/14bed086c5854bba9efafaf664ba5345.png?
[20200817234304562.png]: /images/20221124/5be78391acd54a53b05507a77acc0382.png?