Python: Intersection Point of Two Linked Lists

1. Introduction

In this blog post, we will learn how to write a Python program to find the intersection point of two linked lists.

Finding the intersection point of two linked lists is a common question in computer science. The intersection point refers to a node at which two linked lists merge. Identifying this node can be a helpful exercise in understanding linked list traversal and pointer manipulation.

2. Program Overview

This Python program will achieve the following steps:

1. Define a Node class for linked list nodes.

2. Define methods to calculate the size of the linked lists.

3. Use a two-pointer technique to identify the intersection point.

3. Code Program

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def get_size(head):
    """Calculate size of linked list starting from given head."""
    count = 0
    while head:
        count += 1
        head = head.next
    return count

def find_intersection(head1, head2):
    """Find intersection point of two linked lists."""
    # Calculate sizes of both linked lists
    c1 = get_size(head1)
    c2 = get_size(head2)

    # Calculate difference of sizes
    d = abs(c1 - c2)

    # Make sure head1 points to the bigger list
    if c2 > c1:
        head1, head2 = head2, head1

    # Move the pointer for the bigger list 'd' steps ahead
    for _ in range(d):
        head1 = head1.next

    # Traverse both lists, comparing nodes until we find a match or reach the end
    while head1 and head2:
        if head1 == head2:
            return head1.data
        head1 = head1.next
        head2 = head2.next

    return None

# Sample test
# Creating two linked lists with intersection
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

# First list: 1 -> 2 -> 3
#                      \
#                       4 -> 5
# Second list:          ^
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# Assuming node3 (with value 3) is the intersection point
print(find_intersection(node1, node3))

Output:

3

4. Step By Step Explanation

1. The Node class is used for creating individual nodes of linked lists.

2. The get_size function calculates and returns the size of a linked list starting from the provided head node.

3. In the find_intersection function, we first calculate the sizes of both linked lists.

4. By finding the difference in sizes, we move the pointer of the bigger list ahead by that difference. This ensures that when we traverse both lists simultaneously, they will collide at the intersection.

5. We keep traversing and comparing nodes of both lists until we find a matching node or reach the end of one of the lists.

6. If a match is found, we return the data of that node, otherwise, return None.