面试题：给定N个单链表，找出其中的公共元素并返回结果列表

嘿，这个问题我之前也碰到过类似的场景，核心就是先处理每个链表的去重，再找所有链表的交集对吧？我给你拆解一下思路，再附上具体的代码实现，你一看就懂：

要解决这个问题，关键要抓住两个点：同一链表内去重和多链表找交集，具体步骤如下：

• 第一步：单链表去重：因为题目要求同一链表内的重复元素不算，所以我们可以把每个链表的元素存入集合（哈希表），这样既能自动去重，后续查询交集的效率也很高。
• 第二步：逐步求交集：以第一个链表的去重集合为基准，依次和后面每个链表的去重集合求交集，每一步都更新当前的公共元素集合，直到处理完所有链表。如果中途交集为空，还可以提前终止，节省时间。
• 第三步：保持结果顺序（可选）：如果需要结果和第一个链表中元素的出现顺序一致，就再遍历一次第一个链表，把公共元素按顺序收集起来。

这里我先假设输入的是列表模拟的单链表，如果是真正的单链表结构，只需要修改遍历部分的代码就行，逻辑完全通用：

基础实现版本 #

def get_unique_from_linked_list(linked_list):
    # 处理单链表去重，若为真实单链表，替换为遍历节点的逻辑
    unique_elements = set()
    # 真实单链表遍历写法：
    # current = head_node
    # while current:
    #     unique_elements.add(current.val)
    #     current = current.next
    for num in linked_list:
        unique_elements.add(num)
    return unique_elements

def find_common_elements(lists):
    if not lists:
        return []
    
    # 初始化公共元素集合为第一个链表的去重结果
    common_set = get_unique_from_linked_list(lists[0])
    
    # 依次和后续链表求交集
    for lst in lists[1:]:
        current_unique = get_unique_from_linked_list(lst)
        common_set.intersection_update(current_unique)
        
        # 提前终止：如果当前交集为空，后续也不可能有公共元素了
        if not common_set:
            return []
    
    # 若需要保持第一个链表的元素顺序，按如下方式收集结果
    result = []
    seen = set()
    for num in lists[0]:
        if num in common_set and num not in seen:
            result.append(num)
            seen.add(num)
    
    return result

# 示例测试
list1 = [1, 3, 4, 5, 10, 3]
list2 = [1, 2, 4, 8, 7, 2]
list3 = [9, 11, 1, 4]
print(find_common_elements([list1, list2, list3]))  # 输出: [1, 4]

另一种思路：统计元素出现的链表次数 #

如果链表数量很多，还可以用哈希表统计每个元素在多少个不同的链表中出现，最后筛选出出现次数等于链表总数的元素，这种写法更简洁：

from collections import defaultdict

def find_common_elements_alt(lists):
    if not lists:
        return []
    
    count_map = defaultdict(int)
    # 遍历每个链表，去重后统计元素出现的链表数
    for lst in lists:
        unique_nums = set(lst)
        for num in unique_nums:
            count_map[num] += 1
    
    # 筛选出在所有链表中都出现的元素
    common_nums = {num for num, cnt in count_map.items() if cnt == len(lists)}
    
    # 保持第一个链表的元素顺序
    result = []
    seen = set()
    for num in lists[0]:
        if num in common_nums and num not in seen:
            result.append(num)
            seen.add(num)
    
    return result

# 测试同样输出 [1,4]

• 时间复杂度：两种方法的时间复杂度都是O(total_nodes)，其中total_nodes是所有链表的节点总数，因为每个节点只被遍历一次，集合操作的时间可以忽略不计。
• 空间复杂度：主要消耗在存储去重后的元素，最坏情况下是O(total_nodes)，但实际中因为去重，空间会小很多。

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