### 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:
value = None
next = None

def __init__(self, value, next_node=None):
self.value = value
self.next = next_node

# check if the list has loop
while fast_tract and fast_tract.next:
slow_trace = slow_trace.next
fast_tract = fast_tract.next.next
if slow_trace == fast_tract: return True
return False

# check meet up if list is loop
# todo: infinite loop if not meeting up

# check meet up if list is not loop
while tail_1.next: tail_1 = tail_1.next
while tail_2.next: tail_2 = tail_2.next
return tail_1 == tail_2

# 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)

# 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)

# list 3, separate list
node_1 = Node(1)
node_0 = Node(0, node_1)

# 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

# list 5 same loop with 4
node_25 = Node(25, node_14)
node_24 = Node(24, node_25)

# list 6, separate loop
node_35 = Node(35)
node_34 = Node(34, node_35)
node_35.next = node_34

# checking
print
```#include <iostream>

// node structure
struct Node
{
int value;
Node *next;

Node(int value, Node *next = NULL)
{
this->value = value;
this->next = next;
}
};

// check if the list has loop
{
while (fast_tract && fast_tract->next) {
slow_trace = slow_trace->next;
fast_tract = fast_tract->next->next;
if (slow_trace == fast_tract) return true;
}
return false;
}

// check meet up if list is loop
{
// todo: infinite loop if not meeting up
}
}

// check meet up if list is not loop
{
while (tail_1->next) tail_1 = tail_1->next;
while (tail_2->next) tail_2 = tail_2->next;
return tail_1 == tail_2;
}

int main()
{
// list 1
Node *node_9 = new Node(9);
Node *node_8 = new Node(8, node_9);  // meet of list 1 and 2
Node *node_7 = new Node(7, node_8);
Node *node_6 = new Node(6, node_7);
Node *node_5 = new Node(5, node_6);
printf("%sn", is_loop(head_1) == false ? "true" : "false");

// list 2, will meet with list 1
Node *node_4 = new Node(4, node_8);
Node *node_3 = new Node(3, node_4);
Node *node_2 = new Node(2, node_3);
printf("%sn", is_loop(head_2) == false ? "true" : "false");

// list 3, separate list
Node *node_1 = new Node(1);
Node *node_0 = new Node(0, node_1);
printf("%sn", is_loop(head_3) == false ? "true" : "false");

// list 4 with loop
Node *node_15 = new Node(15);
Node *node_14 = new Node(14, node_15);
Node *node_13 = new Node(13, node_14);
Node *node_12 = new Node(12, node_13);
Node *node_11 = new Node(11, node_12);
node_15->next = node_11;
printf("%sn", is_loop(head_4) ? "true" : "false");  // true

// list 5 same loop with 4
Node *node_25 = new Node(25, node_14);
Node *node_24 = new Node(24, node_25);
printf("%sn", is_loop(head_5) ? "true" : "false");  // true

// list 6, separate loop
Node *node_35 = new Node(35);
Node *node_34 = new Node(34, node_35);
node_35->next = node_34;