Code Destine

Union of two Linked Lists in Java :- 

You have given two linked list, create a linked list containing all the elements of the given two linked list excluding duplicates. i.e. create union of two given linked list. Order of elements in new linked list does not matter.

You can see intersection here, Intersection of two Linked Lists in Java

Algorithm :- 

The algorithm for the implementation of this problem is very simple, here are steps :- 

1. Create a new HashSet.
2. Traverse first linked list.
3. Check data (data stored in the node) is present in a set or not, if it is not present then we create a new node with that data, add it to the new linked list and to the set. Otherwise continue.
4. Repeat step 2 and step 3 for second linked list.

Example Union of two Linked Lists in Java :- 

1) Create a class Node, this class will be a node of our linked list.

package com.codedestine.algorithm.linkedlist;

public class Node {

  private String data;
  private Node next;
 
  public String getData() {
    return data;
  }

  public void setData(String data) {
    this.data = data;
  }

  public Node getNext() {
    return next;
  }

  public void setNext(Node next) {
    this.next = next;
  }
 
}

2) Create a class CreateLinkedList, this class has a method createList which takes string array as an argument and return linked list.

package com.codedestine.algorithm.linkedlist;

public class CreateLinkedList {
 
  public Node createList(String[] dataArr){
    Node listHead = null;
    Node node = null;
    Node tempList = null;
    for(String data : dataArr){
      node = new Node();
      node.setData(data);
      if(listHead == null){
        listHead = node;
        tempList = node;
      }else{
        tempList.setNext(node);
        tempList = node;
      }
    }
    return listHead;
  }

}

3) Create a class UnionLinkedList, this class has a method union which takes two linked list as an argument and return union linked list.

package com.codedestine.algorithm.linkedlist;

import java.util.HashSet;
import java.util.Set;

public class UnionLinkedList {
 
  private Node unionListHeadNode;

  public Node union(Node firstList, Node secondList){ 
    Set<String> uniqueSet = new HashSet<String>();
    Node unionListLastNode = addList(firstList,null,uniqueSet);
    unionListLastNode = addList(secondList,unionListLastNode,uniqueSet);
    return this.unionListHeadNode;
  }
 
  private Node addList(Node sourceList,Node unionListLastNode,Set<String> uniqueSet){
    Node tempNode = null;
    Node tempList = unionListLastNode;
    while(sourceList != null){
      if(!uniqueSet.contains(sourceList.getData())){
        uniqueSet.add(sourceList.getData());
        tempNode = createNode(sourceList.getData());
        if(tempList == null){ 
          tempList = tempNode;
          this.unionListHeadNode = tempList;
        }else{
          tempList.setNext(tempNode);
          tempList = tempNode;
        } 
      }
      sourceList = sourceList.getNext(); 
    }
    return tempList;
  }
 
  private Node createNode(String data){
    Node node = new Node();
    node.setData(data);
    return node;
  }
 
}

4) Create a class Main, this class will be our demo class.

package com.codedestine.algorithm.linkedlist;

public class Main {

  public static void main(String[] args) {
    CreateLinkedList createLinkedList = new CreateLinkedList();
    String[] firstListData = {"a","b","c","d"};
    Node firstList = createLinkedList.createList(firstListData);
    String[] secondListData = {"c","d","e","f"};
    Node secondList = createLinkedList.createList(secondListData);
		
    UnionLinkedList unionLinkedList = new UnionLinkedList();
    Node unionList = unionLinkedList.union(firstList, secondList);
		
    while(unionList != null){
      System.out.println(unionList.getData());
      unionList = unionList.getNext();
    }		
  }

}

Result :- 

That’s all for Union of two Linked Lists in Java, If you liked it, please share your thoughts in a comments section and share it with others too.