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
def is_loop(head):
    if not head: return False
    slow_trace = fast_tract = head
    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
def check_meet_up_with_loop(head_1, head_2):
    # todo: infinite loop if not meeting up
    while head_1 != head_2 and head_1 and head_2:
        head_1 = head_1.next
        head_2 = head_2.next
        if head_2.next: head_2 = head_2.next
    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_meet_up_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

# 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
print 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
print is_loop(head_2) == False

# list 3, separate list
node_1 = Node(1)
node_0 = Node(0, node_1)
head_3 = node_0
print 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
print 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
print 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
print is_loop(head_6)  # true

# checking
print
print check_meet_up_without_loop(head_1, head_2) == True
print check_meet_up_without_loop(head_1, head_3) == False
print check_meet_up_with_loop(head_4, head_5) == True
print check_meet_up_with_loop(head_4, head_6) == False
#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
bool is_loop(Node *head)
{
	if (!head) return false;
	Node *slow_trace = head;
	Node *fast_tract = head;
	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
bool check_meet_up_with_loop(Node *head_1, Node *head_2)
{
	// todo: infinite loop if not meeting up
	while (head_1 != head_2 && head_1 && head_2) {
		head_1 = head_1->next;
		head_2 = head_2->next;
		if (head_2->next) head_2 = head_2->next;
	}
	return head_1 == head_2 && head_1 && head_2;
}

// check meet up if list is not loop
bool check_meet_up_without_loop(Node *head_1, Node *head_2)
{
	Node *tail_1 = head_1;
	Node *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;
}

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);
	Node *head_1 = node_5;
	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);
	Node *head_2 = node_2;
	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);
	Node *head_3 = node_0;
	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;
	Node *head_4 = 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);
	Node *head_5 = node_24;
	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;
	Node *head_6 = node_34;
	printf("%sn", is_loop(head_6) ? "true" : "false");  // true

	// checking
	printf("%sn", check_meet_up_without_loop(head_1, head_2) == true ? "true" : "false");
	printf("%sn", check_meet_up_without_loop(head_1, head_3) == false ? "true" : "false");
	printf("%sn", check_meet_up_with_loop(head_4, head_5) == true ? "true" : "false");
	printf("%sn", check_meet_up_with_loop(head_4, head_6) == false ? "true" : "false");
}

Leave a Reply

%d bloggers like this: