Finding the middle node in a singly linked list involves determining the node that is at the middle position in the list. This can be efficiently achieved using the slow and fast pointer technique.
Consider a singly linked list with the following structure:
Head -> 1 -> 2 -> 3 -> 4 -> 5 -> None
To find the middle node in this list, follow these steps:
After performing these steps, the slow pointer will point to the middle node of the linked list.
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_middle(self):
slow = self.head
fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
print("Linked list:")
linked_list.traverse() # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None
middle_node = linked_list.find_middle()
print("Middle node:", middle_node.data) # Output: 3
This Python program defines a singly linked list with methods for appending nodes, finding the middle node using the slow and fast pointer technique, and traversing the list. The find_middle method returns the middle node of the list.