Home » Link Lists(Nuts & Bolts of CS) » Intersection of twoLinked Lists

Intersection of twoLinked Lists

Method 1(Simply use two loops)
Use 2 nested for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will be O(mn) where m and n are the number of nodes in two lists.

Method 2 (Mark Visited Nodes)
This solution requires modifications to basic linked list data structure. Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse second linked list, If you see a visited node again then there is an intersection point, return the intersecting node. This solution works in O(m+n) but requires additional information with each node. A variation of this solution that doesn’t require modification to basic data structure can be implemented using hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in hash then return the intersecting node.

Method 3(Using difference of node counts)
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

/** Simple (minimal) singly-linked list node. */
class Node {
 int data;
 Node next;
 public Node( int data, Node next ) {
 this.data = data;
 this.next = next;
 }
}

/** Linked-list Utility Methods */
public class Intersection {

private static Node head;

 /** Adds a new element to the head of a list. */
 public void add( int data ) {
 head = new Node( data, head );
 }

 /** Returns a new linked list representing the intersection. */
 public void getIntersection( Node list1, Node list2 ) {

 if( list1 == null || list2 == null ) {
 System.out.print("list is sempty" ); }

 Node cursor1 = list1;
 Node cursor2 = list2;

 while( cursor1 != null && cursor2 != null )
 {
 if( cursor1.data == cursor2.data )
 {
 System.out.print(" "+cursor1.data );

 cursor1 = cursor1.next;
 cursor2 = cursor2.next;
 }
 else if( cursor1.data < cursor2.data ) {
 cursor1 = cursor1.next;
 } else {
 cursor2 = cursor2.next;
 }
 }

 }

 /** Prints the linked-list by traversing it backwards (in reverse). */
 public static void printReverse( Node node ) {
 if( node != null ) {
 printReverse( node.next );
 System.out.print( node.data + " " );
 }
 }

 /** Test Method */
 public static void main( String[ ] args ) {

 // Initialize first list with range [10, 30]
 Intersection list1 = new Intersection( );
 for( int i = 30; i >= 15; i-- ) {
 list1.add( i );
 }

 list1.printReverse( list1.head );
 System.out.println( );

 Intersection list2 = new Intersection( );
 for( int j = 22; j >=15; j-- ) {
 list2.add( j );
 }

 list2.printReverse( list2.head );
 System.out.println( );

 System.out.println( "intersection list :\n");
 Intersection listnew = new Intersection( );

listnew.getIntersection( list1.head, list2.head );

 // Print the intersection in reverse in order to view
 // the entries in ascending order
 ///listnew.printReverse( listnew.head );
 }
}

&nbsp;


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: