12. Intersection point in Y shaped linked lists

12. Intersection point in Y shaped linked lists

Problem link :- click here

package Linked_List;

public class LinkedList__12
{
	/*
	 	Given two singly linked list of size n1 and n2, write a program to  get the point 
	 	where two linked lists intersect each other.
	 					3
	 					 \
	 					  6
	 					   \
	 					    9    10
	 					     \  /
	 					      15
	 					       |
	 					      30
	 					         
	 			list1 = 3-> 6-> 9-> 15-> 30-> null
	 			list2 = 10-> 15-> 30-> null
	 			output : 15
	 	
	 	1 -> we will traverse through the large linked list until size of remaining part of the
	 		list becomes equal to the size of small linked list.
	 	2 -> Now we will traverse through both the linked list simultaneously until 
	 		we find that both the nodes are same.
	 	3 -> return the data of the node
	 */
	
	static int findIntersectPoint(LinkedList list1, LinkedList list2)
	{
		LinkedList small_list=null, long_list=null;
		if(list1.size <= list2.size)
		{
			small_list = list1;
			long_list = list2;
		}
		else
		{
			small_list = list2;
			long_list = list1;
		}
		
		int n1 = long_list.size;
		int n2 = small_list.size;
		
		Node node1 = long_list.head;
		Node node2 = small_list.head;
		
		// step 1 :- traversing through the long list until size becomes equal
		while(n1 != n2)
		{
			node1 = node1.next;
			n1--;
		}
		
		// step 2 :- traversing through both the lists simultaneously until we come to same node
		while(node1 != node2)
		{
			node1 = node1.next;
			node2 = node2.next;
		}
		
		return node1.data;
	}
	
	
	public static void main(String[] args)
	{
		LinkedList list1 = new LinkedList();
		list1.push(3);
		list1.push(6);
		list1.push(9);
		
		LinkedList list2 = new LinkedList();
		list2.push(10);
		
		LinkedList common = new LinkedList();
		common.push(15);
		common.push(30);
		
		list1.head.next.next.next = common.head;
		list2.head.next = common.head;
		
		int ans = findIntersectPoint(list1, list2);
		printList(list1);
		printList(list2);
		printList(common);
		System.out.println("\nIntersection point is : " + 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(1)