Find the Middle Node in a Singly Linked List

Finding the Middle Node

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.

---

Step-by-Step Process

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:

1. Initialize Two Pointers: Start with two pointers, slow and fast, both set to the head of the list.
2. Move Pointers: Move the slow pointer one step at a time and the fast pointer two steps at a time.
3. Check for Middle: When the fast pointer reaches the end of the list (i.e., None), the slow pointer will be at the middle node.
4. Return the Middle Node: The node where the slow pointer is located is the middle node.

After performing these steps, the slow pointer will point to the middle node of the linked list.

---

Python Program to Find the Middle Node in a Singly 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.