How to determine the position of an element in the middle of a linked list, and what is its time complexity?

To find the middle element of a linked list, you can use two pointers: a slow pointer and a fast pointer. The idea is that the fast pointer moves through the list with a step of 2, while the slow pointer moves with a step of 1. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle element.

Example in Java:

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

public Node findMiddle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // slow points to the middle element
}

The time complexity of this algorithm is O(n), where n is the number of elements in the list, since we traverse the list only once.