用hashmap判断两个排序链表的共同项JAVA

Question

我使用了一个散列table来找到两个链表之间的交集。尽管如此，问题是我必须事先给出 table 大小，如果 table 大小大于交集元素， table 将首先填充元素然后打印 0s ( k 是散列的大小 table) 像这样：

Output: Common items are: 2 5 6 0 0 0 0

import java.util.*;

public class LinkedList {
Node head;

static class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;

    }

}

public void printList() {
    Node n = head;
    while (n != null) {
        System.out.print(n.data + " ");
        n = n.next;
    }
}

public void append(int d) {

    Node n = new Node(d);

    if (head == null) {
        head = new Node(d);
        return;
    }

    n.next = null;
    Node last = head;
    while (last.next != null) {
        last = last.next;
    }
    last.next = n;
    return;

}

static int[] intersection(Node tmp1, Node tmp2, int k) {
    int[] res = new int[k];

    HashSet<Integer> set = new HashSet<Integer>();
    while (tmp1 != null) {

        set.add(tmp1.data);
        tmp1 = tmp1.next;

    }

    int cnt = 0;

    while (tmp2 != null) {
        if (set.contains(tmp2.data)) {
            res[cnt] = tmp2.data;
            cnt++;
        }
        tmp2 = tmp2.next;

    }

    return res;

}

public static void main(String[] args) {
    LinkedList ll1 = new LinkedList();
    LinkedList ll2 = new LinkedList();


    ll1.append(1);
    ll1.append(2);
    ll1.append(3);
    ll1.append(4);
    ll1.append(5);
    ll1.append(6);
    ll1.append(7);
    ll1.append(8);

    ll2.append(0);
    ll2.append(2);
    ll2.append(5);
    ll2.append(6);
    ll2.append(9);
    ll2.append(10);
    ll2.append(13);
    ll2.append(14);

    System.out.println("The Linked List 1 size is:  ");


    int[] arr = intersection(ll1.head, ll2.head, 7);

    System.out.print("The Linked List 1 items are: ");
    ll1.printList();

    System.out.print("\nThe Linked List 2 items are: ");
    ll2.printList();

    System.out.print("\nThe Common items are: ");
    for (int i : arr) {
        System.out.print(i + " ");
    }

}}

Answer 1

不要使用数组 - 而是使用（甚至 return）你的 LinkedList 的实例（或 Java 的 List实例）。稍后您可以根据需要轻松地将列表转换为数组 (Convert list to array in Java)

请注意，相乘的零并不是您遇到的最大问题 - 最大的问题是您实际上无法理解第一个零是空元素还是实际上是 0 元素路口的一部分

Answer 2

您可以通过将列表推入两个 Set 并使用 retainAll

来减少您自己的代码

Set<Integer> set1 = new HashSet<Integer>();
while (tmp1 != null) {
    set1.add(tmp1.data);
    tmp1 = tmp1.next;
}
// now all data of your list 1 is stored in set1
Set<Integer> set2 = new HashSet<Integer>();
while (tmp2 != null) {
    set2.add(tmp2.data);
    tmp2 = tmp2.next;
}
// now all data of your list 2 is stored in set2
set1.retainAll(set2);
// now only duplicates are stored in set1

注意 1：re-assign 参数是不好的做法，我更喜欢新的局部变量

注2：去掉数组，你发现了其中一个问题

用hashmap判断两个排序链表的共同项JAVA

Determine the common items between two sorted linked lists with hashmap JAVA

java

arrays

linked-list

hashmap

hashtable