11. Intersection of two sorted linked lists

11. Intersection of two sorted linked lists

Problem link :- click here

package Linked_List;

public class LinkedList__11
{
	/*
	 	Given two lists sorted in increasing order, create a new list representing the 
	 	intersection of the two lists. The new list should be made with its own memory
	 	- original list should not change.
	 			l1 = 1-> 2-> 3-> 4-> 6-> null
	 			l2 = 2-> 4-> 6-> 8-> null
	 		output : 2-> 4-> 6-> null
	 	
	 */
	
	static LinkedList intersectionOfTwoLinkedList(LinkedList list1, LinkedList list2)
	{
		LinkedList intersection = new LinkedList();
		
		Node node1 = list1.head;
		Node node2 = list2.head;
		while(node1 != null  &&  node2 != null)
		{
			if(node1.data  ==  node2.data)
			{
				intersection.push(node1.data);
				node1 = node1.next;
				node2 = node2.next;
			}
			else if(node1.data < node2.data)
				node1 = node1.next;
			else
				node2 = node2.next;
		}
		
		return intersection;
	}
	
	
	public static void main(String[] args)
	{
		LinkedList list1 = new LinkedList();
		list1.push(1);
		list1.push(2);
		list1.push(3);
		list1.push(4);
		list1.push(6);
		
		LinkedList list2 = new LinkedList();
		list2.push(2);
		list2.push(4);
		list2.push(6);
		list2.push(8);
		
		LinkedList ans = intersectionOfTwoLinkedList(list1, list2);
		printList(list1);
		printList(list2);
		System.out.println("\nIntersection of two linked list is : ");
		printList(ans);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n1 + n2)
Space complexity :- O(n1 + n2)