ISourceCode

Make the frequent cases fast and the rare case correct

Y – shaped Linked List. Algorithm to find the node of intersection of two lists.

The algorithm finds the difference in number of nodes and then traverses a list that many times to get the intersecting node.

50->40->30->20->10
             ^
             |  
         80->70  
class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
} 
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public int listLength()
	{
		int counter = 0;
		Node current = first;
		while(current != null)
		{
			current = current.next; 
			counter++;
		}
		return counter;
	}	
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	public static Node firstCommonNode(Node pList1,Node pList2,int length1,int length2)
	{
		
		if (length1 > length2)
		{
			for (int a=0; a < (length1-length2); a++)
			{
				pList1 = pList1.next;
			}
		}
		else
		{
			for (int a=0; a < (length2-length1); a++)
			{
				pList2 = pList2.next;
			}
		}
		while (pList1 != pList2)
		{
			pList1 = pList1.next;
			pList2 = pList2.next;
		}	
		return pList1;
	}
	public Node search(int val)
	{
		Node current = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
				current = current.next;
		}
		return current;
	}

} 
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object1 = new LinkedList();
		LinkedList object2 = new LinkedList();
		object1.insert(10);
		object1.insert(20);
		object1.insert(30);
		object1.insert(40);
		object1.insert(50);
		System.out.println("The first list:");
		object1.display();

		object2.insert(70);
		object2.insert(80);
		
		System.out.println("The second list before intersection:");
		object2.display();

		Node tempObj2 = object2.search(70);
		Node tempObj1 = object1.search(20);
		
		tempObj2.next = tempObj1;
		System.out.println("The second list after intersecting with first list:");
		object2.display();

		int length1 = object1.listLength();
		int length2 = object2.listLength();

		Node head1 = object1.search(50);
		Node head2 = object2.search(80);
		
	
		Node common = object1.firstCommonNode(head1,head2,length1,length2);
		System.out.println("the node of intersection is : " + common.item);
		
	} 
}

OUTPUT:
labuser@ubuntu:~/ListIntersect$ java LinkedListBlog
The first list:
List items from first to last :
[50]
[40]
[30]
[20]
[10]

The second list before intersection:
List items from first to last :
[80]
[70]

The second list after intersecting with first list:
List items from first to last :
[80]
[70]
[20]
[10]

the node of intersection is : 20
labuser@ubuntu:~/ListIntersect$

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: