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

**Calculate the Lengths**: Calculate the lengths of both lists.**Align the Starting Points**: Align the starting points of both lists by advancing the pointer of the longer list by the difference in lengths.**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.