求助：HackerRank好友圈查询问题实现遇阻，合并社群求最大规模

看起来你在处理好友圈合并的逻辑时遇到了瓶颈，我先帮你梳理下当前代码里可能存在的问题，再给出更可靠的实现思路。

当前实现的潜在问题 #

你的代码核心是用personToIndex映射用户到所在圈子的索引，用groups存储每个圈子的NodeList，但这里有几个关键漏洞：

• 合并圈子时的索引更新不完整：当你合并两个圈子list和list2后，只把groups.set(friend2Index, list)，但list2里所有用户的personToIndex映射还是指向原来的friend2Index。这会导致后续查询这些用户时，拿到的索引对应的圈子已经不是他们实际所在的了，后续操作必然出错。
• 圈子实例重复存储：合并后groups中会存在多个指向同一个list的索引，不仅浪费空间，还会让groups的维护变得混乱，比如后续遍历groups时会统计重复的圈子大小。
• 自定义链表的性能瓶颈：每次合并或查询都需要遍历链表，对于大规模数据测试用例，时间复杂度会很高，很容易超时。

你提到用HashSet也遇到同样问题，本质是因为没解决合并后所有用户的归属映射更新这个核心问题，和具体用链表还是HashSet关系不大。

更可靠的解决方案：并查集（Union-Find） #

这个问题属于典型的动态连通性问题，并查集是专门解决这类问题的高效数据结构，时间复杂度接近O(1)，逻辑也更清晰。我给你写一个完整的实现：

import java.util.HashMap;
import java.util.Map;

public class FriendCircleQueries {
    // 存储每个用户的父节点，用于查找所属圈子的根
    private static Map<Integer, Integer> parent = new HashMap<>();
    // 存储每个根节点对应的圈子大小
    private static Map<Integer, Integer> circleSize = new HashMap<>();
    private static int largestCircleSize = 0;

    // 查找用户所在圈子的根节点（带路径压缩，优化后续查询速度）
    private static int find(int person) {
        // 如果用户是第一次出现，初始化自己为根节点，圈子大小为1
        if (!parent.containsKey(person)) {
            parent.put(person, person);
            circleSize.put(person, 1);
            largestCircleSize = Math.max(largestCircleSize, 1);
            return person;
        }
        // 路径压缩：直接把当前节点指向根节点，减少后续查找的层级
        if (parent.get(person) != person) {
            parent.put(person, find(parent.get(person)));
        }
        return parent.get(person);
    }

    // 合并两个用户所在的圈子
    private static void union(int friend1, int friend2) {
        int root1 = find(friend1);
        int root2 = find(friend2);

        // 两人已经在同一个圈子，无需操作
        if (root1 == root2) return;

        // 按秩合并：把小圈子合并到大圈子，保证树的高度尽可能低
        if (circleSize.get(root1) < circleSize.get(root2)) {
            int temp = root1;
            root1 = root2;
            root2 = temp;
        }

        // 把小圈子的根节点指向大圈子的根
        parent.put(root2, root1);
        // 更新大圈子的大小
        circleSize.put(root1, circleSize.get(root1) + circleSize.get(root2));
        // 更新当前最大圈子大小
        largestCircleSize = Math.max(largestCircleSize, circleSize.get(root1));
    }

    // 处理所有查询，返回每次操作后的最大圈子大小
    public static int[] processQueries(int[][] queries) {
        // 重置状态，避免多次调用的干扰
        parent.clear();
        circleSize.clear();
        largestCircleSize = 0;

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            union(queries[i][0], queries[i][1]);
            result[i] = largestCircleSize;
        }
        return result;
    }
}

并查集的优势 #

• 路径压缩：每次查找时都会优化节点的指向，让后续查询几乎是常数时间。
• 按秩合并：始终保持树的高度很低，避免出现退化的链表结构。
• 逻辑简洁：不需要维护复杂的链表或集合，用两个HashMap就能轻松管理用户归属和圈子大小，几乎不会出错。

如果你坚持修复原代码 #

如果一定要用你原来的链表思路，核心要补全的是：

• 合并两个圈子后，遍历被合并圈子（list2）的所有用户，把他们的personToIndex全部更新为目标圈子的索引（friend1Index）。
• 合并后可以把list2从groups中移除，避免后续误操作。但这种方式的时间复杂度是O(n)（n为被合并圈子的用户数），对于大数据量测试用例很容易超时，所以还是更推荐并查集方案。

内容的提问来源于stack exchange，提问作者ghoul932