当前位置：首页 > article >正文

LeetCode热题100-相交链表【JavaScript讲解】

article 2025/1/8 17:07:08

题目：

在这里插入图片描述

分析：

哈希集合是一种特殊的数据结构，用于存储唯一的元素，并允许快速地进行插入、删除和查找操作‌。哈希集合的实现主要依赖于哈希函数和链表。
判断两个链表是否相交，可以使用哈希集合存储链表节点。

‌遍历链表A‌：代码使用一个 while 循环遍历链表 headA。在每次迭代中，将当前节点添加到 visited集合中，并将当前节点更新为下一个节点。这样，当遍历完链表 headA 后，visited 集合中就包含了链表 headA 中的所有节点。
遍历链表B并检查相交‌：然后，代码使用另一个 while 循环遍历链表headB。在每次迭代中，检查当前节点是否存在于 visited集合中。如果存在，说明当前节点是两个链表的相交节点，函数立即返回该节点。如果遍历完链表 headB 后没有找到相交节点，则函数返回null。

题解：

/**
 * 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 visited = new Set();
    let current = headA;
    while(current !== null){
        visited.add(current);
        current = current.next;
    }

    current = headB;
    while(current !== null){
        if(visited.has(current)){
            return current;
        }
        current = current.next;
    }
    return null;
}