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.