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.

1. 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)

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

3. 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"