The Tortoise and Hare method to find the middle element of the linked list

3 min readJun 12, 2022

The idea behind the algorithm is that, if you have two pointers in a linked list, one moves twice as fast (the hare) as the other (the tortoise). By the time the hare completes the whole linked list, the tortoise will be in the middle position !!!.

what is a linked list?

Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. Each node in the linked list will have two things, one is the data and the other is a reference to the next element. The last node will have a null in the reference.

How to find the mid element for the linked list?

Method 1

In this method, we traverse the list once and count the number of nodes(n). Traverse the list again and return the n/2 element if n is even else (n+1)/2.

Code

# Node class
class Node:
    # Function to initialise the node object
    def __init__(self, data):
        self.data = data  # data
        self.next = None  # reference
   
   
# Linked List class
class LinkedList:
   
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Function to insert a new node
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node
 
    # Print the linked list
    def printList(self):
        node = self.head
        while node:
            print(str(node.data) + "->", end="")
            node = node.next
        print("Null")
 
    # Function that returns middle.
    def getMiddle(self):
        # Intialize pointer
        mid = self.head
        List  = self.head
        n = 0
        # Iterate till next is null
        while mid:
            mid = mid.next
            n = n+1
        
        # Finding mid position
        if n%2 ==0:
            n = (n/2)+1
        else:
            n = (n+1)/2
        # Iterate till n is 1
        while n != 1:
            n = n-1
            List = List.next
        # Return the middle element.
        return List.data
        
 
if __name__=='__main__':
   
    # creating object of linked list
    linkedlist = LinkedList()
   
    for i in range(0,6):
        linkedlist.push(i)
        linkedlist.printList()
        print("Middle element is ",linkedlist.getMiddle())while n != 1:
            n = n-1
            temp1 = temp1.next# Return the middle position.
        return temp1.data
        
 
if __name__=='__main__':
   
    # creating object of linked list
    linkedlist = LinkedList()
   
    for i in range(0,6):
        linkedlist.push(i)
        linkedlist.printList()
        print("Middle element is ",linkedlist.getMiddle())

Complexity Analysis

Time Complexity: O(n²)
Space Complexity: O(1)

Method 2: The Tortoise and Hare method

In this method, two-pointers are used to traverse a linked list. One pointer namely slow should be moved one space, while the other pointer namely fast should be moved two spaces. When the fast pointer reaches the end of the linked list, the slow pointer will reach the center. Return the slow pointer value to get the middle element.

Code

# Node class
class Node:
    # Function to initialise the node object
    def __init__(self, data):
        self.data = data  # data
        self.next = None  # reference
   
   
# Linked List class
class LinkedList:
   
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Function to insert a new node
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node
 
    # Print the linked list
    def printList(self):
        node = self.head
        while node:
            print(str(node.data) + "->", end="")
            node = node.next
        print("Null")
 
    # Function that returns middle.
    def getMiddle(self):
        # Intialize two pointers
        slow = self.head
        fast = self.head
 
        # Iterate till fast's next is null
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
         
        # Return the slow's data, which is the middle element.
        return slow.data
 
if __name__=='__main__':
   
    # creating object of linked list
    linkedlist = LinkedList()
   
    for i in range(0,6):
        linkedlist.push(i)
        linkedlist.printList()
        print("Middle element is ",linkedlist.getMiddle())

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

Comparison of Complexity between both Methods

Method 1 has an O(n²) time complexity, however, method 2 has an O(n) time complexity, which is significantly superior.