Find intersection of two Linked Lists

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)

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;
		}
		
	}

}