如何修改给定的LLList交集代码以提升时间效率？

咱们先拆解下你这段代码的核心问题：它用了双重嵌套循环，而且如果LLList是链表实现的话，getItem(i)每次都要从头遍历到第i个元素——这就导致实际的时间复杂度直接飙升到O(n² + n*m)，数据量一大就会慢得离谱。

下面给你两种实用的优化思路，核心都是把查找操作的时间从O(m)降到O(1)，彻底提升效率：

思路一：用HashSet实现O(n+m)时间复杂度 #

这是最常用的优化方式，把其中一个列表的元素存入哈希集合，然后遍历另一个列表快速查找是否存在交集元素。另外，尽量用迭代器遍历链表，避免按索引访问带来的额外遍历开销。

修改后的代码 #

import java.util.HashSet;
import java.util.Iterator;

public static LLList intersect(LLList list1, LLList list2) {
    LLList inters = new LLList();
    HashSet<Object> elementSet = new HashSet<>();
    
    // 优先把更小的列表存入集合，节省内存和初始化时间
    LLList smallerList = list1.length() <= list2.length() ? list1 : list2;
    LLList largerList = list1.length() > list2.length() ? list1 : list2;
    
    // 用迭代器遍历小列表，存入集合
    Iterator<?> iterator = smallerList.iterator();
    while (iterator.hasNext()) {
        elementSet.add(iterator.next());
    }
    
    // 遍历大列表，检查元素是否在集合中
    iterator = largerList.iterator();
    while (iterator.hasNext()) {
        Object currentItem = iterator.next();
        if (elementSet.contains(currentItem)) {
            inters.addItem(currentItem, inters.length());
            // 可选：如果不想保留重复的交集元素，找到后就从集合中移除
            // elementSet.remove(currentItem);
        }
    }
    
    return inters;
}

关键优化点解释 #

• 哈希集合的快速查找：HashSet的contains()方法是O(1)时间复杂度，彻底替代了原代码中内层循环的O(m)查找
• 选择小列表存集合：如果两个列表大小差异大，存小列表能减少内存占用和初始化集合的时间
• 迭代器遍历：链表按索引getItem(i)是O(i)时间，迭代器遍历是O(1)步进到下一个元素，避免了重复从头遍历链表的开销
• 去重选项：如果原列表有重复元素，你可以在找到交集元素后调用elementSet.remove(currentItem)，这样结果里不会出现重复的交集元素

思路二：先排序再双指针遍历（适用于可排序的元素） #

如果LLList中的元素是可排序的（比如实现了Comparable接口），还可以先把两个列表排序，然后用双指针遍历，时间复杂度主要由排序的O(n logn + m logm)决定，适合内存有限、不想用哈希集合的场景。

示例代码（假设元素可排序） #

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public static LLList intersect(LLList list1, LLList list2) {
    LLList inters = new LLList();
    
    // 把LLList转成可排序的List并排序
    List<Object> sortedList1 = convertToSortedList(list1);
    List<Object> sortedList2 = convertToSortedList(list2);
    
    int i = 0, j = 0;
    while (i < sortedList1.size() && j < sortedList2.size()) {
        Comparable<?> item1 = (Comparable<?>) sortedList1.get(i);
        Comparable<?> item2 = (Comparable<?>) sortedList2.get(j);
        int compareResult = item1.compareTo(item2);
        
        if (compareResult == 0) {
            inters.addItem(item1, inters.length());
            i++;
            j++;
            // 去重：跳过重复元素
            while (i < sortedList1.size() && sortedList1.get(i).equals(sortedList1.get(i-1))) {
                i++;
            }
            while (j < sortedList2.size() && sortedList2.get(j).equals(sortedList2.get(j-1))) {
                j++;
            }
        } else if (compareResult < 0) {
            i++;
        } else {
            j++;
        }
    }
    
    return inters;
}

// 辅助方法：把LLList转成排序后的List
private static List<Object> convertToSortedList(LLList llList) {
    List<Object> list = new ArrayList<>();
    Iterator<?> iterator = llList.iterator();
    while (iterator.hasNext()) {
        list.add(iterator.next());
    }
    Collections.sort((List<Comparable>) list);
    return list;
}

原代码的效率问题复盘 #

原代码的双重循环+按索引访问链表，导致：

• 外层循环遍历list1的n个元素，每次getItem(i)需要从头遍历到第i个元素，总时间O(n²)
• 内层循环遍历list2的m个元素，每次getItem(j)同样是O(j)时间，总时间O(nm)
  整体时间复杂度是O(n² + nm)，当n和m达到千级以上时，性能会断崖式下降。

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