Find intersection of two Linked Lists

Two linked lists A and B are joined on a particular node, called the point of intersection of the linked lists. Find the point of intersection, i.e. the first node after which both lists have same nodes.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Naive Solution:
Keep a node in List A as fixed and iterate over all nodes in List B to check if there is a node in List B same as the fixed node from List A.
1. Take two loops - outer loop for iterating over list A. Inner loop for list B.
2. In inner loop, check if a node matches current node of A.
3. If found, return the node, else move to next node.
4. If not found, return null.

Time Complexity: O(n*m)
Space Complexity: O(1)

Solution using a Hash:
1. Iterate over first list and put the nodes in a hash set.
2. Iterate over other list and find the first node that is present in the hash set. This node is the intersection of the 2 lists.

Time Complexity: O(n+m)
Space Complexity: O(n)


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.saurabh.questions;

import java.util.HashSet;
/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Linked List Intersection</b><br>
 * Two linked lists list1 and list2 are joined a particular node, called the point of intersection of the linked lists. 
 * Find the point of intersection, i.e. the first node after which both lists have same nodes.
 * 
 * Example: <br>
 * List1: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - X
 * <br>
 * List2: 11 - 12 - 13 - 14 - 15 - 5 - 6 - 7 - 8 - 9 - 10 - X
 * <br>
 * <br>
 * Output: 5
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=l936ym8yDSo">Linked List Intersection Youtube Link</a> 
 * @author Saurabh
 *
 */
public class FindLinkedListIntersectionByHash {

	private Node head;

	public Node getHead() {
		return head;
	}

	public void setHead(Node head) {
		this.head = head;
	}
	
	// Solution 1: 
	// Time Complexity: O(n*m)
	// Space Complexity: O(1)
	public static Node getIntersectionOfLists(Node aList, Node bList) {
		
		Node a = aList;
		while(a != null) {	
			Node b = bList;
			while(b != null) {
				
				if(a == b) {
					return a;
				}
				b = b.getNext();
			}
			a = a.getNext();
		}
		
		return null;
	}
	
	// Solution 2: 
	// Time Complexity: O(n+m)
	// Space Complexity: O(n)
	public static Node getIntersectionOfListsUsingHash(Node aList, Node bList) {
		
		if(aList == null || bList == null) {
			return null;
		}
		
		HashSet<Node> set = new HashSet<Node>();
		
		Node a = aList;
		while(a != null) {
			set.add(a);
			a = a.getNext();
		}
		
		Node b = bList;
		while(b != null) {
			if(set.contains(b)) {
				return b;
			}
			b = b.getNext();
		}
		return null;
	}
	
	/* ************************************************
	 * Test linked list intersection
	 * ************************************************
	 */
    public void addToList(int num) {
		
		if(head == null) {
			head = new Node(num);
			return;
		}
		
		Node tmp = head;
		while(tmp.getNext() != null) {
			tmp = tmp.getNext();
		}
		tmp.setNext(new Node(num));
	}
	
	public static void main(String[] args) {
		FindLinkedListIntersectionByHash list1 = new FindLinkedListIntersectionByHash();
		int i = 1;
		int n = 5;
		while(i <= n) {
			list1.addToList(i);
			i++;
		}
		
		FindLinkedListIntersectionByHash list2 = new FindLinkedListIntersectionByHash();
		i = 11;
		n = 15;
		while(i <= n) {
			list2.addToList(i);
			i++;
		}
		
		Node tmp1 = list1.getHead();
		i = 1;
		n = 5;
		while(i < n) {
			tmp1 = tmp1.getNext();
			i++;
		}
		
		Node tmp2 = list2.getHead();
		while(tmp2.getNext() != null) {
			tmp2 = tmp2.getNext();
		}
		tmp2.setNext(tmp1);
		
		Node intersection = getIntersectionOfListsUsingHash(list1.getHead(), list2.getHead());
		if(intersection != null) {
		    System.out.println("Intersection of linked lists found at Node " + intersection.getData());
		} else {
			System.out.println("Linked lists do not intersect!");
		}
	}

	class Node {

		private int data;
		private Node next;

		public Node(int data) {
			this.data = data;		
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}
		
	}

}
		

Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer