Two Sorted Linked List Intersections in Java
Make a new list that represents the intersections of the two lists, and then return it, given two lists that are ordered in increasing order. The new list must be created from scratch using its own memory; the original lists must not be altered.
Example
First linked list input: 1-> 2->3-> 4-> 6
2->4->6->8 is the second linked list.
Results: 2->4->6.
Common elements include 2, 4, and 6.
the list and the order in which they list intersections.
Utilizing Dummy Node
The strategy is to start the output list with a dummy as well as a temporary node. In order to add or append additional nodes fast, the tail reference is indeed a pointer that points to the output list's last node. The tail has a memory space to point to thanks to the temporary node. Keep in mind that the tail pointer initially directs attention to the return dummy node.
The current challenge is to use a single loop to loop over the provided linked list. Keep in mind that if one of the linked lists is entirely explored, the loop will end. The two-pointer technique is employed in the loop. One pointer, ptr1, and another, ptr2, for linked lists 1 and 2, respectively. The next three situations are as follows:
- The value pointed to by ptr1 is bigger than the value pointed to by ptr2,
- Value reference by ptr1 is lower than value pointer by ptr2, which is the case.
- Both ptr1 and ptr2 point to the same value.
Increase ptr2 to refer to the following node for case 1. For scenario 2, increase ptr1 to indicate the following node. Print this value and the increment for Case 3; both pointers should point to the following node. In example 3, we need to take proper care of the linked list nodes that have the same value. For instance,
Linked list 1: 4->4->4->4->4->4->4->5
Linked list 2: 4->4->4->4->5
The very first node in both the linked list and in this instance is 4, therefore case 3 applies. As a result, we print the number 4 and raise ptr1 through ptr2 to point at the subsequent node. However, even after being increased, both ptr1 and ptr2 still point to the number 4.
As a result, we must once more increment both pointers. However, this time, since 4 has already been printed, we won't display that value; instead, we will keep increasing the pointers until they both point to 5.
The results are 4 and 5.
Example Program
// Program for two sorted linked list intersections in java using a dummy node approach
public class LinkedListIntersection
{
static LinkedLstNode p1 = null;
static LinkedLstNode p2 = null;
static LinkedLstNodedmy = null;
static LinkedLstNodetl = null;
static class LinkedLstNode
{
int val;
LinkedLstNode next;
LinkedLstNode(int v)
{
this.val = v;
next = null;
}
}
void displayList(LinkedLstNodest)
{
LinkedLstNodeptr = st;
while (ptr != null)
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
void push(int v)
{
LinkedLstNode t = new LinkedLstNode(v);
if(dmy == null)
{
dmy = t;
tl = t;
}
else
{
tl.next = t;
tl = t;
}
}
void intersectEle()
{
LinkedLstNode ptr1 = p1;
LinkedLstNode ptr2 = p2;
int tempVal = -1;
while(ptr1 != null && ptr2 != null)
{
if(ptr1.val == ptr2.val)
{
if(tempVal != ptr1.val)
{
push(ptr1.val);
tempVal = ptr1.val;
}
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
else if(ptr1.val < ptr2.val)
{
ptr1 = ptr1.next;
}
else
ptr2 = ptr2.next;
}
}
public static void main(String args[])
{
LinkedListIntersectionll = new LinkedListIntersection();
ll.p1 = new LinkedLstNode(13);
ll.p1.next = new LinkedLstNode(14);
ll.p1.next.next = new LinkedLstNode(36);
ll.p1.next.next.next = new LinkedLstNode(41);
ll.p1.next.next.next.next = new LinkedLstNode(57);
ll.p1.next.next.next.next.next = new LinkedLstNode(90);
ll.p1.next.next.next.next.next.next = new LinkedLstNode(91);
ll.p1.next.next.next.next.next.next.next = new LinkedLstNode(93);
ll.p2 = new LinkedLstNode(10);
ll.p2.next = new LinkedLstNode(11);
ll.p2.next.next = new LinkedLstNode(16);
ll.p2.next.next.next = new LinkedLstNode(31);
ll.p2.next.next.next.next = new LinkedLstNode(41);
ll.p2.next.next.next.next.next = new LinkedLstNode(86);
ll.p2.next.next.next.next.next.next = new LinkedLstNode(91);
ll.p2.next.next.next.next.next.next.next = new LinkedLstNode(93);
ll.intersectEle();
System.out.println("The first list is: ");
ll.displayList(p1);
System.out.println();
System.out.println("The second list is: ");
ll.displayList(p2);
System.out.println();
System.out.println("The matched elements of the first linked list, as well as the second linked list, are: ");
ll.displayList(dmy);
ll.p1 = null;
ll.p2 = null;
ll.dmy = null;
ll.p1 = new LinkedLstNode(1);
ll.p1.next = new LinkedLstNode(1);
ll.p1.next.next = new LinkedLstNode(1);
ll.p1.next.next.next = new LinkedLstNode(1);
ll.p1.next.next.next.next = new LinkedLstNode(1);
ll.p1.next.next.next.next.next = new LinkedLstNode(3);
ll.p2 = new LinkedLstNode(1);
ll.p2.next = new LinkedLstNode(1);
ll.p2.next.next = new LinkedLstNode(1);
ll.p2.next.next.next = new LinkedLstNode(3);
System.out.println("\n \n");
ll.intersectEle();
ll.displayList(p1);
System.out.println();
System.out.println("The second list is: ");
ll.displayList(p2);
System.out.println();
System.out.println("The matched elements of the first linked list, as well as the second linked list, are: ");
ll.displayList(dmy);
}
}
The output of the above program
The first linked list is:
13 14 36 41 57 90 91 93
The second list is:
10 11 16 31 41 86 91 93
The matched elements of the first linked list, as well as the second linked list, are:
41 91 93
The first list is:
1 1 1 1 1 3
The second list is:
1 1 1 3
The matched elements of the first linked list, as well as the second linked list, are:
1 3
Analysis of Complexity:
O(m+n) time complexity, where m and n are the first as well as second linked lists' respective node counts.
The list traversals only need to be done once.
Space Auxiliary: O(min(m, n)).
min(m,n) nodes can be stored in the output list at most.
Utilizing Hashing
Given that we are aware that HashSet in Java only contains singular members, we can utilize this feature to identify the shared elements between the two linked lists. Take note of the program below.
Program
// Program for two sorted linked list intersections in java using a dummy node approach
import java.util.*;
public class LinkedListIntersection2
{
static LinkedLstNode p1 = null;
static LinkedLstNode p2 = null;
static class LinkedLstNode
{
int val;
LinkedLstNode next;
LinkedLstNode(int v)
{
this.val = v;
next = null;
}
}
public void displayList(ArrayList<Integer>aList)
{
int size = aList.size();
for(int i = 0; i< size; i++)
{
System.out.print(aList.get(i) + " ");
}
}
void displayLinkedList(LinkedLstNodest)
{
LinkedLstNodeptr = st;
while (ptr != null)
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
public ArrayList<Integer>intersectionList(LinkedLstNode t1, LinkedLstNode t2)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
HashSet<Integer> set1 = new HashSet<Integer>();
HashSet<Integer> set2 = new HashSet<Integer>();
while(t1 != null)
{
set1.add(t1.val);
t1 = t1.next;
}
while(t2 != null)
{
set2.add(t2.val);
t2 = t2.next;
}
for (Integer i : set1)
{
if(set2.contains(i))
{
temp.add(i);
}
}
return temp;
}
public static void main(String[] args)
{
LinkedListIntersection2 ll = new LinkedListIntersection2();
ll.p1 = new LinkedLstNode(13);
ll.p1.next = new LinkedLstNode(15);
ll.p1.next.next = new LinkedLstNode(36);
ll.p1.next.next.next = new LinkedLstNode(41);
ll.p1.next.next.next.next = new LinkedLstNode(57);
ll.p1.next.next.next.next.next = new LinkedLstNode(90);
ll.p1.next.next.next.next.next.next = new LinkedLstNode(91);
ll.p1.next.next.next.next.next.next.next = new LinkedLstNode(93);
ll.p2 = new LinkedLstNode(10);
ll.p2.next = new LinkedLstNode(15);
ll.p2.next.next = new LinkedLstNode(16);
ll.p2.next.next.next = new LinkedLstNode(31);
ll.p2.next.next.next.next = new LinkedLstNode(41);
ll.p2.next.next.next.next.next = new LinkedLstNode(86);
ll.p2.next.next.next.next.next.next = new LinkedLstNode(91);
ll.p2.next.next.next.next.next.next.next = new LinkedLstNode(93);
System.out.println("The first list is: ");
ll.displayLinkedList(p1);
System.out.println();
System.out.println("The second list is: ");
ll.displayLinkedList(p2);
System.out.println();
ArrayList<Integer> al = ll.intersectionList(ll.p1, ll.p2);
System.out.println("The matched elements of the first linked list, as well as the second linked list, are: ");
ll.displayList(al);
ll.p1 = null;
ll.p2 = null;
ll.p1 = new LinkedLstNode(7);
ll.p1.next = new LinkedLstNode(7);
ll.p1.next.next = new LinkedLstNode(7);
ll.p1.next.next.next = new LinkedLstNode(7);
ll.p1.next.next.next.next = new LinkedLstNode(7);
ll.p1.next.next.next.next.next = new LinkedLstNode(6);
ll.p2 = new LinkedLstNode(7);
ll.p2.next = new LinkedLstNode(7);
ll.p2.next.next = new LinkedLstNode(7);
ll.p2.next.next.next = new LinkedLstNode(6);
System.out.println("\n \n");
al = ll.intersectionList(ll.p1, ll.p2);
System.out.println("The first linked list is: ");
ll.displayLinkedList(p1);
System.out.println();
System.out.println("The second linked list is: ");
ll.displayLinkedList(p2);
System.out.println();
System.out.println("The matched elements of the first linked list as well as the second linked list are: ");
ll.displayList(al);
}
}
The output of the above program
The first list is:
13 15 36 41 57 90 91 93
The second list is:
10 15 16 31 41 86 91 93
The matched elements of the first linked list, as well as the second linked list, are:
41 91 93 15
The first list is:
7 7 7 7 7 6
The second list is:
7 7 7 6
The matched elements of the first linked list, as well as the second linked list, are:
6 7
Analysis of Complexity:
The complexity of Time: O (n)
Additional Space: O(n) as adding additional space
Utilizing recursion technique
// Program for two sorted linked list intersections in java using a recursion method
public class LinkedListIntersection
{
static LinkedLstNode p1 = null;
static LinkedLstNode p2 = null;
static LinkedLstNode head = null;
static LinkedLstNode tail = null;
static LinkedLstNodedmy = null;
static class LinkedLstNode
{
int val;
LinkedLstNode next;
LinkedLstNode(int v)
{
this.val = v;
next = null;
}
}
void displayList(LinkedLstNodest)
{
LinkedLstNodeptr = st;
while (ptr != null)
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
public void intersectEle(LinkedLstNode ptr1, LinkedLstNode ptr2)
{
if (ptr1 == null || ptr2 == null)
{
return;
}
if (ptr1.val < ptr2.val)
{
intersectEle(ptr1.next, ptr2);
}
else if (ptr1.val > ptr2.val)
{
intersectEle(ptr1, ptr2.next);
}
else
{
LinkedLstNode temp = new LinkedLstNode(ptr1.val);
if(head == null)
{
head = temp;
tail = temp;
}
else if(tail.val != temp.val)
{
tail.next = temp;
tail = tail.next;
}
intersectEle(ptr1.next, ptr2.next);
}
}
public static void main(String args[])
{
LinkedListIntersection1 ll = new LinkedListIntersection1();
ll.p1 = new LinkedLstNode(13);
ll.p1.next = new LinkedLstNode(14);
ll.p1.next.next = new LinkedLstNode(36);
ll.p1.next.next.next = new LinkedLstNode(41);
ll.p1.next.next.next.next = new LinkedLstNode(57);
ll.p1.next.next.next.next.next = new LinkedLstNode(90);
ll.p1.next.next.next.next.next.next = new LinkedLstNode(91);
ll.p1.next.next.next.next.next.next.next = new LinkedLstNode(93);
ll.p2 = new LinkedLstNode(10);
ll.p2.next = new LinkedLstNode(15);
ll.p2.next.next = new LinkedLstNode(16);
ll.p2.next.next.next = new LinkedLstNode(31);
ll.p2.next.next.next.next = new LinkedLstNode(41);
ll.p2.next.next.next.next.next = new LinkedLstNode(86);
ll.p2.next.next.next.next.next.next = new LinkedLstNode(91);
ll.p2.next.next.next.next.next.next.next = new LinkedLstNode(93);
ll.intersectEle(ll.p1, ll.p2);
System.out.println("The first linked list is: ");
ll.displayList(p1);
System.out.println();
System.out.println("The second linked list is: ");
ll.displayList(p2);
System.out.println();
System.out.println("The common elements of the first linked list and the second linked list are: ");
ll.displayList(ll.head);
ll.p1 = null;
ll.p2 = null;
ll.head = null;
ll.tail = null;
ll.p1 = new LinkedLstNode(4);
ll.p1.next = new LinkedLstNode(4);
ll.p1.next.next = new LinkedLstNode(4);
ll.p1.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next.next = new LinkedLstNode(5);
ll.p2 = new LinkedLstNode(4);
ll.p2.next = new LinkedLstNode(4);
ll.p2.next.next = new LinkedLstNode(4);
ll.p2.next.next.next = new LinkedLstNode(5);
System.out.println("\n \n");
ll.intersectEle(ll.p1, ll.p2);
System.out.println("The first list is: ");
ll.displayList(p1);
System.out.println();
System.out.println("The second list is: ");
ll.displayList(p2);
System.out.println();
System.out.println("The matched elements of the first linked list, as well as the second linked list, are: ");
ll.displayList(ll.head);
}
}
The output of the above program
The first list is: 13 14 36 41 57 90 91 93
The second list is:
10 15 16 31 41 86 91 93
The matched elements of the first linked list, as well as the second linked list,are:
41 91 93
The first list is:
4 4 4 4 4 5
The second list is:
4 4 4 5
The common elements of the first linked and the second linked list is:
4 5
Analysis of Complexity:
O(m+n) time complexity, where m and n are the first as well as second linked lists' respective node counts.