如何在 O(n) 时间复杂度内找出两个链表之间缺失的元素？

Question

我有两个整数的单向链表。其中一个是另一个的子集（数字顺序不同）。找到第一个链表包含但第二个链表不包含的数字，最好的方法（关于性能）是什么？

我的想法是首先对它们进行排序（使用归并排序），然后逐个比较元素。所以，它需要O(nlogn+mlogm+n)的时间，但应该存在一个更好的O(n)解决方案。

- tammy

---

更好的解决方案是不使用链表来表示集合，而是使用 Set。 - Gene

@Gene 问题的提问者可能需要保持顺序（因为他/她提到顺序不同），尽管在这里使用 Set 可能会有用。 - user2864740

对于两个小列表，O(n*m)的暴力算法可能是“最快”的。我想这些序列的规模相当大，但要记得找到并专注于实际的瓶颈。 - user2864740

@user2864740 然后他应该使用 LinkedHashSet。http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html - Gene

@Gene 这可能是另一种可能性。然而，我不知道代码使用了什么（其他）算法，以至于首先使用了某种链表。 - user2864740

Answer 1

这是一个时间和空间复杂度均为O(n)的解决方案。

逻辑如下：假设原始链表大小为N，我们称之为LL1，第二个链表为LL2。

首先，准备一个大小为N的哈希表，其中key是LL1中的数字，value是LL2中该数字的频率。

 HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();

=> 开始遍历 LL1 并将所有数字的频率设置为 0
当所有 LL1 中的值被迭代时，您就拥有了所有数字在 HashMap 中出现的频率为 0。

 map.put(key, 0);

=> 现在开始循环遍历LL2，使用它们作为键来选择数字，并将其值增加1。
当所有LL2中的值都被迭代时，您就拥有了HashMap中同时存在于LL1和LL2中的所有公共数字，其frequency > 0

  map.put(key, map.get(key) + 1);

=> 现在开始遍历 hasmap，搜索 value = 0，当找到时，将 key 打印出来，因为这个数字只存在于 LL1 中而不在 LL2 中。

for (map.Entry<Integer,Integer> entry : map.entrySet())
{
    if(entry.getValue() == 0)
        System.out.println(entry.getKey());//This is a loner
}

使用O(n)时间和O(n)内存进行2次迭代。

- NoobEditor

Answer 2

你可以将它们放在不同的映射中，然后进行比较。将其放在一个映射中应该是m和n的两个单独的for循环，并且映射的查找时间为1。

- StackFlowed

---

只需要一个 Map/Set：将其填充为第一个列表的内容，然后在迭代第二个列表时进行探测。 - user2864740

请提供一些代码片段。随意编辑答案。 - StackFlowed

Answer 3

HashSet是在这种情况下使用的最佳数据结构。 使用此代码，您可以在O（n）中实现结果。 如果您有更多条件，请告诉我，我可以相应地提供建议。

 public class LinkedList {

        private ListNode head;

        public ListNode getHead() {
            return head;
        }
    }

    public class ListNode {

        public int value;
        public ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public class UtilClass{
       public static int checkLists(LinkedList list1, LinkedList list){
            ListNode head = myList2.getHead();

            HashSet<Integer> hashSet = new HashSet<Integer>();

            while(head!=null){
                hashSet.add(head.value);
                head = head.next;
            }

            head = myList.getHead();

            while(head!=null){
                boolean b = hashSet.add(head.value);
                if(b == true) return head.value;
                head = head.next;
            }
             return -1111;
    }
    }

- user892871

Answer 4

你可以使用 removeAll 方法。你所需要做的就是创建一个接受两个列表的方法，一个是原始列表，另一个是子列表，然后返回一个缺失元素的列表：

List getMissing(List original, List sub){
     original.removeAll(sub);
     return original;
}

虽然这个运行时间为二次方，但如果你真的想要强制它在线性时间O(n)内运行，那么你必须编写自定义类来包装你的输入，以便对于每个输入，都有一个标志来监视是否已将其添加到子列表中。您还可以设计一个类，它可以在监视两个列表内容的同时促进元素的添加和删除。

- blitz

Answer 5

令N = m+n。

• 将列表相加。由于它们是链接列表，因此成本很低 O(1)。
• 对它们进行排序 O(N log N) - 也许最好使用 ArrayList。
• 遍历列表，如果找不到连续的一对{x, x}，则找到了一个缺失的元素，O(N)，因为第二个列表是子集。

所以 O(N . log N)。

由于列表未排序，任何加速都包括类似排序的操作，而这会增加成本。因此 O(N.log N) 是可以接受的。

如果您想要 O(N)，可以按以下方式执行（简化，使用正数）：

BitSet present = new BitSet(Integer.MAX_VALUE);
for (int value : sublist)
    present.set(value);
for (int value : list)
    if (!present.isSet(value)) {
        System.out.println("Missing: " + value);
        break;
    }

这是在内存与时间之间做出的权衡。需要注意的是，这个答案可能不被接受，因为内存大小是2^MAX_VALUE，初始化/清除所需的时间也很长。

可能的O(N log N)解决方案

最聪明的答案可能是协作排序两个列表，并在排序过程中检测缺失的元素。类似于随意选择一个“中位数”元素并移动索引以分割列表，并采取分治的方法。

如果列表大小相差1

那么你只需要对每个列表进行求和，差值就是缺失的值：O(N)。可以处理溢出。

- Joop Eggen