findMid - geeks4geeks

findMid.py

"""
https://practice.geeksforgeeks.org/problems/finding-middle-element-in-a-linked-list/1

- Use "tortoise and the hare" method to find the middle
- Use a pointer that increments half the "speed" of another pointer
"""
def findMid(head):
    
    if head is None:
        return None
    
    tortoise = head
    hare = head
    
    while (hare is not None and hare.next is not None):
    
        # the tortoise moves half the speed of the hare
        tortoise = tortoise.next
        
        # the hare moves twice as fast
        hare = hare.next.next
        
    return tortoise

#{ 
#  Driver Code Starts
# Node Class    
class node:
    def __init__(self, val):
        self.data = val
        self.next = None
        
# Linked List Class
class Linked_List:
    def __init__(self):
        self.head = None

    def insert(self, val):
        if self.head == None:
            self.head = node(val)
        else:
            new_node = node(val)
            temp = self.head
            while(temp.next):
                temp=temp.next
            temp.next = new_node

def createList(arr, n):
    lis = Linked_List()
    for i in range(n):
        lis.insert(arr[i])
    return lis.head

if __name__=='__main__':
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int, input().strip().split()))
        head = createList(arr, n)
        print(findMid(head).data)
        
# } Driver Code Ends