# 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:

1. The value pointed to by ptr1 is bigger than the value pointed to by ptr2,
2. Value reference by ptr1 is lower than value pointer by ptr2, which is the case.
3. 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,

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
{
{
int val;
{
this.val = v;
next = null;
}
}
{
while (ptr != null)
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
void push(int v)
{
if(dmy == null)
{
dmy = t;
tl = t;
}
else
{
tl.next = t;
tl = t;
}
}
void intersectEle()
{
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[])
{
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;

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.*;
{
{
int val;
{
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) + " ");
}
}
{
while (ptr != null)
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
{
ArrayList<Integer> temp = new ArrayList<Integer>();
HashSet<Integer> set1 = new HashSet<Integer>();
HashSet<Integer> set2 = new HashSet<Integer>();
while(t1 != null)
{
t1 = t1.next;
}
while(t2 != null)
{
t2 = t2.next;
}
for (Integer i : set1)
{
if(set2.contains(i))
{
}
}
return temp;
}
public static void main(String[] args)
{
System.out.println("The first list is: ");
System.out.println();
System.out.println("The second  list is: ");
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;
System.out.println("\n \n");
al = ll.intersectionList(ll.p1, ll.p2);
System.out.println("The first linked list is: ");
System.out.println();
System.out.println("The second linked list is: ");
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)

### Utilizing recursion technique

// Program for two sorted linked list intersections in java using a recursion method

``````public class LinkedListIntersection
{
{
int val;
{
this.val = v;
next = null;
}
}
{
while (ptr != null)
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
{
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
{
{
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[])
{
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.p1 = null;
ll.p2 = null;
ll.tail = null;

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

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.