Katkat
Back

Detect overlap of two linked lists with cycles

AirbnbSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to detect if two linked lists merge, specifically when they may contain cycles, by requiring logic to identify loop entry points and intersection nodes.

Problem Statement

You are given two linked lists, each of which may or may not contain a cycle. Determine if these two lists intersect and return the node where they first overlap. If they do not intersect, return null.

Two lists intersect if they share the same memory node. If both lists have cycles, they may intersect before, at, or after the loop entry point. If the lists intersect, they will share the remainder of their structure.

Function Signature

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_intersection(head1: Node, head2: Node) -> Node:
    pass

Constraints

  • The lists can be of length 0 to 10^5.
  • val is an integer.
  • Time complexity should be O(N + M) where N and M are the lengths of the lists.
  • Space complexity should be O(1).

Examples

Example 1: No cycles Input: List A (1 -> 2 -> 3), List B (4 -> 3) Output: Node(3) Explanation: Both lists converge at node 3.

Example 2: Both lists contain cycles Input: Two lists that loop back on themselves at different points and merge into a shared cycle. Output: The first node where the two paths meet.

Edge Cases

  • One list has a cycle and the other does not (these cannot intersect).
  • Lists are empty.
  • Intersection occurs at the start of a cycle.

Hints

Hint 1

First, use Floyd's cycle-finding algorithm (tortoise and hare) to determine if each list has a cycle and find the entry point of the loop.

Hint 2

If one list has a cycle and the other doesn't, they cannot intersect; if both have cycles, check if the entry nodes are the same or if the loops overlap.

Hint 3

For acyclic lists, calculate the lengths to align them, or use the two-pointer 'reset' approach to find the intersection node in linear time.

Follow-up questions

  • How does your algorithm change if you are not allowed to modify the linked list nodes (e.g., cannot set temporary flags)?
  • What if the lists could have multiple intersection points before forming a cycle? Does the problem definition remain valid?
  • How would you handle the case where the two lists share the same cycle but enter it at different nodes?