I used a hashtable to find the intersection between the two linked lists. Still, the problem is that I have to give the table size beforehand and if the table size is > intersection elements the table will be filled with the elements first and then it prints 0s (k is the size of the hashtable) like this:

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   " ");
    }

}}

CodePudding user response：

You can reduce your own code by pushing your lists into two Sets and use 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

Note 1: it's bad practice to re-assign parameters, I prefer new local variables

Note 2: get rid of arrays, you found one of their problems

CodePudding user response：

Do not use array - instead use (or even return) an instance of your LinkedList (or Java's List instance). Later you can easily transform the list to the array if necessary (Convert list to array in Java)

Please notice that the multiplied zeroes are not the biggest issue you have - the biggest issue is that you are actually not able to understand whether the first zero is just empty element or actually 0 element that is the part of intersection