剑指 Offer 52. 两个链表的第一个公共节点_心得技巧

上一篇: 用Python写春联，我还是第一次见下一篇:go语言之 go简介及go开发工具安装

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

发布时间：2022-06-25 发布网站：脚本宝典

脚本宝典收集整理的这篇文章主要介绍了剑指 Offer 52. 两个链表的第一个公共节点，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

一、题目要求

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

二、题目分析

　　1.找到相同值，我们可以选择用set来解决问题，用map要定义值，set更快，先遍历headA放到Set里，然后在把B遍历一遍，每个值和set里进行比较，找到输出该值，如果都没有就输出null

　　2.双指针：借用一下别人的图，注意比较的是物理地址不是数值，就像下图一样；

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

三、代码分析

/**
 * 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 p1 = headA, p2 = headB;
    if( headA == null || headB == null){
        return null;
    }

    while( p1 != p2){
       p1 = p1 == null? headB:p1.next;
       p2 = p2 == null? headA:p2.next;
    }

    return p1;
};

/**
 * 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 tmp = new Set();
    while( headA != null){
        tmp.add(headA);
        headA = headA.next;
    }
    while( headB!=null){
        if(tmp.has(headB)){
            return headB;
        }
        headB = headB.next;
    }

    return null;
};