algorithm to find if two linked lists are intersected

Two different lists will be intersected when one node of a list points to the other list’s node.

The below diagram depicts the intersection of lists
IntersectedSLL
How do you solve it:

  • Get the difference of the two lists (In above diagram it is 5-4=1)
  • Take a pointer to the bigger list and move it as many number of times as difference between the lists calculated above (bigger list with 5 nodes is moved 1 position forward with pointer1 pointing to 2)
  • Take another pointer to the second list and start comparing node of first list with the node of the second list. (Take pointer2 pointing to 18)
  • Whenever nodes are same we can say lists are intersected. (they get intersected at node 4)

Code:

/**
	 * Algorithm to detect the intersecting point of two lists
	 *
	 * @param s1 first list which is larger in size
	 * @param s2 second list
	 */
	public static void getIntersectPoint(SLLIntersection s1,SLLIntersection s2){
		int s1Len = s1.getLength(s1.root);
		int s2Len = s2.getLength(s2.root);

		int diff = s1Len-s2Len;
		System.out.println("Difference between two lists is "+diff);

		// Move the pointer in the larger list to diff places
		SLLNode s1List = s1.root;
		if((s1Len-s2Len)>0) {
			while((s1List != null) && diff>0){
				s1List = s1List.next;
				diff--;
			}
		}

		// Now check the point where the lists are intersecting
		// by checking each node in two lists simultaneously
		SLLNode s2List = s2.root;
		while(s1List != null && s1List.next != null) {
			if(s1List == s2List) {
				System.out.println("Intersection point is at "+s1List.value);
			}
			// increment the pointers
			s1List = s1List.next;
			s2List = s2List.next;
		}
	}

Output:

List1: 1 2 3 4 5
List2: 18 19 4 5
Difference between two lists is 1
Intersection point is at 4
Advertisements

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

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey