Can you find the middle of a linked list?

We can certainly find the middle of a linked list using two pointer technique also known as the "Runner Technique”.

This method involves initializing two pointers at the head of the list: a ‘slow‘ pointer and a ‘fast‘ pointer. The slow pointer will iterate one node at a time, while the fast pointer will move two nodes at once. When the ‘fast‘ pointer reaches the end of the linked list, the ‘slow‘ pointer will be at the middle.

Here’s a Python example:

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

def find_middle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data

# Creating the linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

# Find the middle
print(find_middle(head))  # Output: 3

This algorithm works in O(n) time, where n is the length of the linked list, and in O(1) space, because we’re using a constant amount of space.

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

def find_middle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data