Determine If Two Linked Lists Intersect
Question
Given 2 linked list head pointers, determine whether they intersect at some point.
Solution
First of all, linked list can have loop or not, and this gives 3 possible situations.

For the 2 loops head pointer 1 and head pointer 2, move pointer 1 at normal speed, and pointer 2 at double speed. If they intersect, node will be the same at some point. Otherwise infinity loop occurs. (need to be fixed)

For 2 straight linked list, they would have the same tails if they intersect.

For a loop and a straight list, use the first algorithm and let the loop to move at double speed. If they donâ€™t intersect, tail of the straight list will end the checking.
So one of the key idea is to check if a linked list is loop. Since loop may start not at the head, we can not use head pointer as the checking reference. We could instead use the algorithm 1 against itself, if it has loop the 2 moving pointer will meet at some point.
Sample Code
# node structure
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
# check if the list has loop and return the length of the list
def is_loop(head):
if not head: return 0
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
count = 1
slow = slow.next
while(slow != fast):
slow = slow.next
count += 1
return count
return 0
# check meet up if list is loop
def check_intersect_with_loop(head_1, head_2, length_1, length_2): # todo: infinite loop if not meeting up
counter = length_1 * length_2
while head_1 != head_2 and head_1 and head_2 and counter > 0:
head_1 = head_1.next
head_2 = head_2.next
if head_2.next: head_2 = head_2.next
counter = 1
return head_1 == head_2 and head_1 is not None and head_2 is not None
# check meet up if list is not loop
def check_intersect_without_loop(head_1, head_2):
tail_1 = head_1
tail_2 = head_2
while tail_1.next: tail_1 = tail_1.next
while tail_2.next: tail_2 = tail_2.next
return tail_1 == tail_2
# combine both
def check_intersect(head_1, head_2):
loop_length_list_1 = is_loop(head_1)
loop_length_list_2 = is_loop(head_2)
if loop_length_list_1 > 0 and loop_length_list_2 > 0:
print '> check_intersect_with_loop'
return check_intersect_with_loop(head_1, head_2, loop_length_list_1, loop_length_list_2)
elif loop_length_list_1 == 0 and loop_length_list_2 == 0:
print '> check_intersect_without_loop'
return check_intersect_without_loop(head_1, head_2)
return False
# list 1
node_9 = Node(9)
node_8 = Node(8, node_9) # meet of list 1 and 2
node_7 = Node(7, node_8)
node_6 = Node(6, node_7)
node_5 = Node(5, node_6)
head_1 = node_5
assert is_loop(head_1) == False
# list 2, will meet with list 1
node_4 = Node(4, node_8)
node_3 = Node(3, node_4)
node_2 = Node(2, node_3)
head_2 = node_2
assert is_loop(head_2) == False
# list 3, separate list
node_1 = Node(1)
node_0 = Node(0, node_1)
head_3 = node_0
assert is_loop(head_3) == False
# list 4 with loop
node_15 = Node(15)
node_14 = Node(14, node_15)
node_13 = Node(13, node_14)
node_12 = Node(12, node_13)
node_11 = Node(11, node_12)
node_15.next = node_11
head_4 = node_11
assert is_loop(head_4) # true
# list 5 same loop with 4
node_25 = Node(25, node_14)
node_24 = Node(24, node_25)
head_5 = node_24
assert is_loop(head_5) # true
# list 6, separate loop
node_35 = Node(35)
node_34 = Node(34, node_35)
node_35.next = node_34
head_6 = node_34
assert is_loop(head_6) # true
# checking print
print "checking list 1 and 2"
assert check_intersect(head_1, head_2) == True
print "checking list 1 and 3"
assert check_intersect(head_1, head_3) == False
print "checking list 4 and 5"
assert check_intersect(head_4, head_5) == True
print "checking list 4 and 6"
assert check_intersect(head_4, head_6) == False
print "all good"