Find the Intersection Point of Two Singly Linked Lists

Introduction to Finding the Intersection Point of Two Singly Linked Lists

Finding the intersection point of two singly linked lists involves determining the node at which the two lists intersect. This can be achieved by comparing the nodes of both lists or using two-pointer techniques.

---

Step-by-Step Process

Consider two singly linked lists with the following structures before intersection:

List 1: Head1 -> 1 -> 2 -> 3 \
                            -> 6 -> 7 -> 8 -> None
List 2: Head2 -> 4 -> 5 /

To find the intersection point, follow these steps:

1. Calculate the Lengths: Calculate the lengths of both lists.
2. Align the Starting Points: Align the starting points of both lists by advancing the pointer of the longer list by the difference in lengths.
3. Traverse Both Lists: Traverse both lists simultaneously until a common node is found or the end is reached.

After performing these steps, the node at which the lists intersect will be identified.

---

Pseudo Code

Function find_intersection(head1, head2):
    len1 = get_length(head1)
    len2 = get_length(head2)
    
    diff = abs(len1 - len2)
    
    If len1 > len2:
        longer = head1
        shorter = head2
    Else:
        longer = head2
        shorter = head1
    
    For i from 0 to diff-1:
        longer = longer.next
    
    While longer is not null and shorter is not null:
        If longer == shorter:
            Return longer
        longer = longer.next
        shorter = shorter.next
    
    Return null

Function get_length(head):
    length = 0
    current = head
    While current is not null:
        length += 1
        current = current.next
    Return length

---

Python Program to Find the Intersection Point of Two Singly Linked Lists

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def find_length(self):
        length = 0
        current = self.head
        while current:
            length += 1
            current = current.next
        return length

    def find_intersection(self, other):
        len1 = self.find_length()
        len2 = other.find_length()

        diff = abs(len1 - len2)

        longer = self.head if len1 > len2 else other.head
        shorter = other.head if len1 > len2 else self.head

        for _ in range(diff):
            longer = longer.next

        while longer and shorter:
            if longer == shorter:
                return longer
            longer = longer.next
            shorter = shorter.next

        return None

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
list1 = SinglyLinkedList()
list1.append(1)
list1.append(2)
list1.append(3)
list1.append(6)
list1.append(7)
list1.append(8)
print("List 1:")
list1.traverse()  # Output: 1 -> 2 -> 3 -> 6 -> 7 -> 8 -> None

list2 = SinglyLinkedList()
list2.append(4)
list2.append(5)
# Creating intersection
list2.head.next.next = list1.head.next.next.next  # 4 -> 5 -> 6
print("List 2:")
list2.traverse()  # Output: 4 -> 5 -> 6 -> 7 -> 8 -> None

intersection_node = list1.find_intersection(list2)
if intersection_node:
    print(f"Intersection at node with data: {intersection_node.data}")  # Output: Intersection at node with data: 6
else:
    print("No intersection found")

This Python program defines a singly linked list with methods for appending nodes, finding the length, finding the intersection point with another list, and traversing the list. The find_intersection method identifies the node at which the two lists intersect.