Skip to main content
1 of 2
JavaDeveloper
  • 8.4k
  • 29
  • 92
  • 159

Find union and intersection of linkedlist

Find the union and intersection of linkedlist, given that elements dont repeat in a single linkedlist. This question is attributed to GeeksForGeeks. Looking for code-review, optimizations and best practices.

public class IntersectionAndUnionLinkedList<T> {

    private Node<T> first;
    private Node<T> last;
    private int size;

    
    public IntersectionAndUnionLinkedList() {}
    
    public IntersectionAndUnionLinkedList(List<T> items ) {
        for (T item : items) {
            add (item);
        }
    }
    
    public void add(T item) { 
        Node<T> node = new Node<T>(item);
        if (first == null) {
            first = last = node;
        } else {
            last.next = node;
            last = last.next;
        }
        size++;
    }
    
    
    private static class Node<T> {
        private T item;
        private Node<T> next;
        
        Node (T item) {
            this.item = item;
        }
    }
    
    
    public IntersectionAndUnionLinkedList<T> intersection(IntersectionAndUnionLinkedList<T> list) {
        final Set<T> items = new HashSet<>();
        Node<T> smallerListNode;
        Node<T> largerListNode;
        
        if (list.size < size) {
            smallerListNode = list.first;
            largerListNode = first;
        } else {
            smallerListNode = first;
            largerListNode = list.first;
        }
        
        while (smallerListNode != null) {
            items.add(smallerListNode.item); 
            smallerListNode = smallerListNode.next;
        } 
        
         
        IntersectionAndUnionLinkedList<T> intersectionlist = new IntersectionAndUnionLinkedList<>();
        while (largerListNode != null && items.size() > 0) { 
            if (items.contains(largerListNode.item)) {
                intersectionlist.add(largerListNode.item);
                items.remove(largerListNode.item);
            } 
            largerListNode = largerListNode.next;
        }
        
        return intersectionlist;
    }
    
    
    public IntersectionAndUnionLinkedList<T> union(IntersectionAndUnionLinkedList<T> list) {
        final Set<T> items = new HashSet<>();
        Node<T> smallerListNode;
        Node<T> largerListNode;
        
        if (list.size < size) {
            smallerListNode = list.first;
            largerListNode = first;
        } else {
            smallerListNode = first;
            largerListNode = list.first;
        }
        
        IntersectionAndUnionLinkedList<T> intersectionlist = new IntersectionAndUnionLinkedList<>();
        while (smallerListNode != null) {
            items.add(smallerListNode.item); 
            intersectionlist.add(smallerListNode.item);
            smallerListNode = smallerListNode.next;
          
        }
       
        while (largerListNode != null) { 
            if (!items.contains(largerListNode.item)) {
                intersectionlist.add(largerListNode.item);
            } 
            largerListNode = largerListNode.next;
        }
        
        return intersectionlist;
    }
    
    
    // size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
    public List<T> toList() {
        List<T> list = new ArrayList<>();
        if (first == null) return list;
        
        for (Node<T> x = first; x != null; x = x.next) {
            list.add(x.item);
        }
         
        return list;
    }
    
    
    @Override
    public int hashCode() {
        int hashCode = 1;
        for (Node x = first; x != null; x = x.next)
            hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        IntersectionAndUnionLinkedList<T> other = (IntersectionAndUnionLinkedList) obj;
        Node<T> currentListNode = first; 
        Node<T> otherListNode =  other.first;
       
        while (currentListNode != null && otherListNode != null) {
            if (currentListNode.item != otherListNode.item) return false;
            currentListNode = currentListNode.next;
            otherListNode = otherListNode.next;
        }
        return currentListNode == null && otherListNode == null;
    }
}



public class IntersectionAndUnionLLTest {

    
    @Test
    public void intersection() {
        IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        IntersectionAndUnionLinkedList<Integer> ll2 = new IntersectionAndUnionLinkedList<>(Arrays.asList(3, 4, 5, 6, 7));
        
        IntersectionAndUnionLinkedList<Integer> llExpected1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(3, 4, 5));
        assertEquals(llExpected1, ll1.intersection(ll2));
    }
    
    @Test
    public void union() {
        IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        IntersectionAndUnionLinkedList<Integer> ll2 = new IntersectionAndUnionLinkedList<>(Arrays.asList(3, 4, 5, 6, 7));
        
        IntersectionAndUnionLinkedList<Integer> llExpected2 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        assertEquals(llExpected2, ll1.union(ll2));
    }
    
    @Test
    public void intersectionNull() {
        IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        IntersectionAndUnionLinkedList<Integer> ll3 = new IntersectionAndUnionLinkedList<>();
        IntersectionAndUnionLinkedList<Integer> llExpected3 = new IntersectionAndUnionLinkedList<>();
        assertEquals(llExpected3, ll1.intersection(ll3));
    }
    
    @Test
    public void unionNull() {
        IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        IntersectionAndUnionLinkedList<Integer> ll4 = new IntersectionAndUnionLinkedList<>();
        IntersectionAndUnionLinkedList<Integer> llExpected4 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        assertEquals(llExpected4, ll1.union(ll4));
    }
    
}
JavaDeveloper
  • 8.4k
  • 29
  • 92
  • 159