Problem

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

Intersection point means end of one linked list is linked with some node in another linked list and it forms a Y shape.

Input: Two Linked List Output: Intersection Node or point, find Intersection Point in Two Linked List

Examples

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

begin to intersect at node c1.

Example 1:

A:         4 → 1
                  ↘
                     8 → 4 → 5
                  ↗
B:     5 → 6 → 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'

Example 2:

A:     2 → 6 → 4
B:     1 → 5

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection

Notes

  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Solution

Method 1 - Simply Use 2 Loops

Algorithm

  • Implement two for loops, with the outer iterating over each node in the first list, and the inner looping through the second list.
  • During each iteration of the inner loop, compare nodes in the second list against the current node from the first list.

Code

Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	while (headA != null) {
		ListNode temp = headB;

		while (temp != null) {
			if (temp == headA)
				return headA;
			temp = temp.next;
		}

		headA = headA.next;
	}

	return null;
}

Complexity

  • ⏰ Time complexity: O(m.n), with ’m’ and ’n’ representing the counts of nodes in the first and second lists, respectively.
  • 🧺 Space complexity: O(1)

Method 2 - Add visited flag to linked list node

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)

Complexity

  • ⏰ Time complexity: O(m+n), with ’m’ and ’n’ representing the counts of nodes in the first and second lists, respectively. But this requires additional information with each node.
  • 🧺 Space complexity: O(1)

Method 3 - Using visited hashset

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.

Code

Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	Set<ListNode> set = new HashSet<>();

	while (headA != null) {
		set.add(headA);
		headA = headA.next;
	}

	while (headB != null) {
		if (set.contains(headB)) {
			return headB;
		}
		headB = headB.next;
	}

	return null;
}

Complexity

  • ⏰ Time complexity: O(m+n), with ’m’ and ’n’ representing the counts of nodes in the first and second lists, respectively. But this requires additional information with each node.
  • 🧺 Space complexity: O(m) as we store only first node

Method 4 - Use Length Difference of 2 Linked Lists 🥈

Algorithm

  • Find length difference: Calculate the absolute difference (lenDiff) between lengths of lists A (a_len) and B (b_len).
  • Traverse longer list: Move the pointer of the longer list by lenDiff nodes.
  • Simultaneous traversal: Iterate through both lists simultaneously.
  • Intersection check: If the current nodes are the same, it’s the intersection point.
  • No intersection: If either list pointer reaches the end, there’s no intersection.

Code

Java
public ListNode getIntersectedNode(ListNode head1, ListNode head2) {
	int c1 = getCount(head1);
	int c2 = getCount(head2);
	int d;

	if (c1 > c2) {
		d = c1 - c2;
		return getIntersectionGivenLengthDelta(d, head1, head2);
	} else {
		d = c2 - c1;
		return getIntersectionGivenLengthDelta(d, head2, head1);
	}
}

private int getCount(Node node) {
	Node current = node;
	int count = 0;

	while (current != null) {
		count++;
		current = current.next;
	}

	return count;
}

private ListNode getIntersectionGivenLengthDelta(int d, Node head1, Node head2) {
	int i;
	Node current1 = head1;
	Node current2 = head2;
	for (i = 0; i<d; i++) {
		if (current1 == null) {
			return null;
		}
		current1 = current1.next;
	}
	while (current1 != null && current2 != null) {
		if (current1.val == current2.val) {
			return current1.val;
		}
		current1 = current1.next;
		current2 = current2.next;
	}

	return null;
}

Slightly cleaner code:

public ListNode getIntersectionNode(ListNode head1, ListNode head2) {
	int l1 = getLength(head1);
	int l2 = getLength(head2);

	int diff = Math.abs(l1 - l2);
	ListNode big = l1 > l2 ? head1 : head2;
	ListNode small = l1 <= l2 ? head1 : head2;

	while(diff > 0){
		big = big.next;
		diff--;
	}

	while(big != null && small != null){
		if(big == small){
			return big;
		}
		big = big.next;
		small = small.next;
	}

	return null;
}

public  int getLength(ListNode head) {
	ListNode curr = head;
	int length = 0;
	while (curr != null) {
		length++;
		curr = curr.next;
	}
	return length;
}

Complexity

  • ⏰ Time complexity: O(m+n)
  • 🧺 Space complexity: O(1)

Method 5 - Without Knowing the Exact Length Difference 🏆

Consider below linked lists A and B as our example:

  • Yellow circles represent nodes unique to list A.
  • Green circles represent nodes unique to list B.
  • The first blue circle is the intersection point we’re looking for.

Since, we have already seen that the lists might have unequal lengths before the intersection, simply iterating and comparing nodes won’t work.

Observations

Observation 1 - They share tail nodes

Regardless of their lengths, both lists share the same tail nodes after the intersection point.

Observation 2 - Merged lists length is equal

While both lists may have different lengths, the combined length of list A and list B remains the same regardless of the order (list A + list B or list B + list A).

Algorithm

We don’t have to create modified list but instead we can simultaneously loop on A and B.

  1. Start the loop on list A with pointer say a. Once listA is over, start with listB
  2. Simultaneously, start the loop on list B with pointer say b. Once listB is over, start with listB
  3. Continue with step 1 and 2, till we have a!=b. When, a==b, we break, because we are guaranteed that the last nodes of both iterations will be our blue nodes.

What if There’s No Intersection?

In that case, we would like for our loop will stop when we’ve reached the end of both combined lists. That is, when both our node pointers are null. Luckily, as you’ll see in the code, our while loop’s exist condition accounts for this edge case as well.

Code

Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) { // loop until we found the first common node
        a = a == null ? headB : a.next; // once we're done with A, move to B
        b = b == null ? headA : b.next; // once we're done with B, move to A
	}
	return a;
}

Dry Run

            a
A:          a1 → a2
                   ↘
                     c1 → c2 → c3 → null
                   ↗            
B:     b1 → b2 → b3
       b

                 a
A:          a1 → a2
                   ↘
                     c1 → c2 → c3 → null
                   ↗            
B:     b1 → b2 → b3
            b

A:          a1 → a2
                   ↘ a
                     c1 → c2 → c3 → null
                   ↗            
B:     b1 → b2 → b3
                 b

A:          a1 → a2
                   ↘      a
                     c1 → c2 → c3 → null
                   ↗ b           
B:     b1 → b2 → b3

A:          a1 → a2
                   ↘           a
                     c1 → c2 → c3 → null
                   ↗      b           
B:     b1 → b2 → b3

A:          a1 → a2
                   ↘                a = null, then a = b1
                     c1 → c2 → c3 → null
                   ↗           b           
B:     b1 → b2 → b3

A:          a1 → a2
                   ↘ 
                     c1 → c2 → c3 → null
                   ↗                b = null, then b = a1 
B:     b1 → b2 → b3
       a

            b         
A:          a1 → a2
                   ↘ 
                     c1 → c2 → c3 → null
                   ↗
B:     b1 → b2 → b3
            a

                 b         
A:          a1 → a2
                   ↘ 
                     c1 → c2 → c3 → null
                   ↗ 
B:     b1 → b2 → b3
                 a

A:          a1 → a2
                   ↘ b
                     c1 → c2 → c3 → null
                   ↗ a
B:     b1 → b2 → b3
a == b => we break, and return either of a OR b. In our code we return a = c1.

Method 5 - Make Circle in First List

Algorithm

  1. This method involves modifying the first list by converting it into a circular linked list (remembering the last node for later).
  2. Then, the problem is transformed into finding start of the loop in the second list aka Linked List Cycle 2 - Find Start of a Cycle.
  3. Knowing the first list’s length (loop size), traverse the second list that many nodes. Start another pointer from the beginning of the second list.
  4. Iterate until these pointers meet, which indicates the intersection point.
  5. Finally, revert the first list back to its original state.

Code

Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	if (headA == null || headB == null) return null;
	// find last node of list A (c3)
	ListNode endA = headA;
	while (endA.next != null) {
		endA = endA.next;
	}
	// join c3 to b1 making a c1...c3-b1...b3-c1 loop (if b3 indeed points to c1)
	endA.next = headB;

	ListNode start = null; // if there's no cycle this will stay null
	// Floyd's cycle finder
	ListNode slow = headA, fast = headA;
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) { // found a cycle
			// reset to beginning to find cycle start point (c1)
			start = headA;
			while (slow != start) {
				slow = slow.next;
				start = start.next;
			}
			break;
		}
	}
	// unjoin c3-b1
	endA.next = null;
	return start;
}