Learn
Technical Interview Problems in Python: Linked Lists
Find Merge Point

Nodes within a linked list can be referenced multiple times. We’ll explore this idea with a partially merged linked list.

# a -> b # \ # -> c -> e # / # d -> f

In this example, two different heads (nodes holding 'a' and 'd') merge into a single linked list with the node holding 'c'. This “merge point” results from nodes holding 'b' and 'f' both referencing the node holding 'c' as the .next property.

Write a function that returns the merge point node of two linked lists if it exists.

# x -> a -> b # \ # -> q -> e # / # d -> f # node holding 'q' # r # \ # -> x # / # f # node holding 'x' # j -> k # l -> q # None

To recap:

  • write a function: merge_point().
  • merge_point() takes two arguments, both instances of a linked list.
  • return the first node referenced by both linked lists, or None if such a node does not exist.

Instructions

1.

See if you can solve this problem in linear, O(N), time complexity.

Another solution runs in quadratic, O(N * M), time complexity. N is the length of one linked list and M refers to the other.

We detail our approach in the hint.

Folder Icon

Sign up to start coding

Already have an account?