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

Intersection of twoLinked Lists

Advertisements

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;

Advertisements

2 Comments

  1. Bonjour,

    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key Intersection of twoLinked Lists in the entire space.

    We were experimenting with AWS and somehow linked existing accounts. If I click the button to say close account then I get a message stating: AWS Training USA

    I look forward to see your next updates.

    ,Merci

    Ajeeth

  2. Ajeeth Kapoor says:

    Hi Buddie,

    Your writing shines like gold! There is no room for gibberish here clearly. You nailed it in Intersection of twoLinked Lists

    Detailed Billing Report with Resources and Tags will be unavailable at later date. May I know when will this later date be? We are using Detailed Billing Report with Resources and Tags to analyze AWS billing. AWS Training

    Awesome! Thanks for putting this all in one place. Very useful!

    Thanks a heaps,
    Ajeeth

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: