0

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

}}
Aziz Mlayel
  • 3
  • 4
  • You could change `int[] res` to `List res` so there's no need to care about the size – Stefan Warminski May 16 '22 at 10:58
  • 1
    I’m very sure, there is a reason why the task description contains the information that the lists are *sorted*. You are supposed to utilize the sorted nature of the lists. You don’t need a `HashSet` and you don’t need two loops to find the intersection. – Holger May 16 '22 at 12:42
  • @Holger what do you suggest? – Aziz Mlayel May 16 '22 at 13:03
  • 1
    I think you are supposed to think about it on your own. However, if you have no clue, think about the following: Start with the first nodes of the two lists 1.) compare the values of the nodes, 2) if equal, add the value to intersection and advance both nodes to the next, otherwise, advance the node with the lower value to the next node 3) go to step 1, repeating until reaching both lists’ ends or, if you reach the end of one list and the other’s node has a bigger value, you can stop as there can’t be an intersection in the remainder. – Holger May 16 '22 at 13:47

2 Answers2

0

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

m.antkowicz
  • 13,268
  • 18
  • 37
0

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

Stefan Warminski
  • 1,845
  • 1
  • 9
  • 18
  • `static Set intersection(Node tmp1, Node tmp2) { Set set1 = new HashSet(); while (tmp1 != null) { set1.add(tmp1.data); tmp1 = tmp1.next; } // now all data of your list 1 is stored in set1 Set set2 = new HashSet(); while (tmp2 != null) { set2.add(tmp2.data); tmp2 = tmp2.next; } // now all data of your list 2 is stored in set2 set1.retainAll(set2); return set1; }` – Aziz Mlayel May 16 '22 at 12:54
  • sorry i'm still not used to website that's why the code is like that – Aziz Mlayel May 16 '22 at 13:06