Find middle element of a linked list in single pass

Linked lists are a fundamental data structure used in computer science for organizing and managing data. A linked list is a linear collection of elements, where each element (called a node) contains data and a reference (or link) to the next node in the sequence. One of the main advantages of a linked list is that it allows efficient insertion and deletion of elements, as opposed to arrays, where resizing can be a costly operation.

In this blog post, we’ll explore a problem that many developers face while working with linked lists: how to find the middle element of a linked list in a single pass. Finding the middle element is a common operation in many algorithms, and it is important to do so efficiently, especially when working with large lists.

Typically, you might think that finding the middle element requires traversing the entire list twice—first to get the length of the list and then to find the middle. However, using a simple yet effective technique known as the two-pointer (runner) approach, we can solve this problem in one pass.

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


class SinglyLinkedList:

    def __init__(self):
        self.head = None

    def push(self, new_data):
        """Add element at the beginning"""
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def pushLast(self, new_data):
        """Add element at the end"""
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node

    def findMiddle(self):
        """Find the middle element using single pass (two-pointer approach)"""
        slow = self.head
        fast = self.head

        # Traverse the list with fast pointer moving twice as fast as slow
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        if slow:
            print("Middle element is:", slow.data)
        else:
            print("The list is empty.")

    def __str__(self):
        """Return string representation of the list"""
        result = []
        temp = self.head
        while temp:
            result.append(str(temp.data))
            temp = temp.next
        return " -> ".join(result) if result else "[Empty List]"


# Main program
s = SinglyLinkedList()

print("Linked List Menu:")
print("1: Add element at the beginning")
print("2: Add element at the end")
print("3: Find middle element")
print("4: Display the linked list")
print("0: Exit")

while True:
    try:
        choice = int(input("\nEnter your choice: "))
    except ValueError:
        print("[INVALID INPUT]: Please enter a valid number.")
        continue

    if choice == 0:
        print("Exiting program.")
        break
    elif choice == 1:
        data = input("Enter element to add at beginning: ")
        s.push(data)
    elif choice == 2:
        data = input("Enter element to add at end: ")
        s.pushLast(data)
    elif choice == 3:
        s.findMiddle()
    elif choice == 4:
        print("Linked list contents:")
        print(s)
    else:
        print("[INVALID INPUT]: Please enter a valid menu option.")

Output

Enter your choice: 1
Enter element to add at beginning: 3

Enter your choice: 
[INVALID INPUT]: Please enter a valid number.

Enter your choice: 1
Enter element to add at beginning: 6

Enter your choice: 1
Enter element to add at beginning: 4

Enter your choice: 9
[INVALID INPUT]: Please enter a valid menu option.

Enter your choice: 1
Enter element to add at beginning: 4

Enter your choice: 3
Middle element is: 6

Enter your choice: 0
Exiting program.