Python Program to Find the Intersection Point of Two Linked Lists

Overview

This Python program finds the intersection point of two singly linked lists. The intersection point is where the two linked lists share common nodes. The program uses a two-pointer approach to efficiently determine the point of intersection.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list and a function to find the intersection point of two linked lists.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has two attributes: data (the value of the node) and next (pointer to the next node).
2. Create a function get_intersection_node that takes the head nodes of two linked lists and returns the intersection point.
3. To find the intersection point, calculate the lengths of both lists.
4. Move the pointer of the longer list ahead by the difference in lengths to align both lists at the same distance from the end.
5. Traverse both lists simultaneously. The point where both pointers are equal is the intersection point.

Python Code


class Node:
"""
Node class to represent a linked list node.
Each node contains the data and a pointer to the next node.
"""
def __init__(self, data):
self.data = data
self.next = None

def get_length(head):
“””
Calculate the length of a linked list.

:param head: Head node of the linked list
:return: Length of the linked list
“””
length = 0
current = head
while current:
length += 1
current = current.next
return length

def get_intersection_node(head1, head2):
“””
Find the intersection point of two linked lists.

:param head1: Head node of the first linked list
:param head2: Head node of the second linked list
:return: The intersection node, or None if no intersection
“””
# Get the lengths of both linked lists
length1 = get_length(head1)
length2 = get_length(head2)

# Calculate the difference in lengths
diff = abs(length1 – length2)

# Adjust the pointers to the longer list
if length1 > length2:
for _ in range(diff):
head1 = head1.next
else:
for _ in range(diff):
head2 = head2.next

# Traverse both lists simultaneously to find the intersection
while head1 and head2:
if head1 == head2:
return head1 # Intersection point found
head1 = head1.next
head2 = head2.next

return None # No intersection

# Helper function to print a linked list
def print_linked_list(head):
“””
Print the elements of a linked list starting from the head node.

:param head: Head node of the linked list
“””
current = head
while current is not None:
print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create two linked lists
# List 1: 1 -> 2 -> 3 -> 4 -> 5
# List 2: 9 -> 4 -> 5 (intersection at node with value 4)
common = Node(4)
common.next = Node(5)

head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = common

head2 = Node(9)
head2.next = common

print(“Linked List 1:”)
print_linked_list(head1)

print(“Linked List 2:”)
print_linked_list(head2)

# Find intersection
intersection = get_intersection_node(head1, head2)
if intersection:
print(f”Intersection at node with data: {intersection.data}”)
else:
print(“No intersection found.”)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data) and a reference to the next node (next).
• get_length function: Calculates the length of a linked list by traversing all nodes.
• get_intersection_node function: Finds the intersection point by first aligning the two linked lists based on their lengths and then traversing them simultaneously to detect the intersection node.
• print_linked_list function: A utility function to display both linked lists for clarity.

Example Output

Given the two linked lists:

• List 1: 1 -> 2 -> 3 -> 4 -> 5 -> None
• List 2: 9 -> 4 -> 5 -> None

The intersection point will be at node with value:

4