Find the middle element of a singly Linked List

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 15 minutes

The problem we are exploring is to find the middle element of a singly linked list. For instance, if the linked list is 1 -> 2 -> 3 -> 4 -> 5, then the middle element is 3. If there are even number of elements in a linked list such as 1 -> 2 -> 3 -> 4 -> 5 -> 6, then the middle element is 3 and 4.

There are two (2) approaches to solve this problem:

Using two (2) traversal of the linked list
One traversal: Using slow and fast pointers

Approach 1: Using two traversals

The idea is to use one traversal to count the number of elements (say n) in a linked list and use another traversal to find the middle element that is the n/2 th element of the Linked List.

Pseudocode

Pseudocode of the algorithm to find the middle element of a linked list using two traversals:


// one traversal
int count_elements(Node head)
{
    int count = 0;
    if(head != null) ++ count;
    
    Node temp = head;
    while(temp.next != null)
    {
        ++ count;
        temp = temp.next;
    }
    return count;
}

// second traversal
int middle_element(int count, Node head)
{
    int middle = (int)count/2;
    Node temp = head;
    
    while(middle > 0)
    {
        temp = temp.next;
        -- middle;
    }
    
    return temp.data; // middle element
}

Complexity

Worst case time complexity: Θ(N)
Average case time complexity: Θ(N)
Best case time complexity: Θ(N)
Space complexity: Θ(1)

Implementations

Java

Java


class LinkedList 
{ 
    static Node head; // head of linked list 
    private class Node 
    { 
        int data; 
        Node next;
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
    static int count()
    {
        Node temp = head;
        int count = 0;
        while(temp != null)
        {
            ++ count;
            temp = temp.next;
        }
        return count;
    }
    void middle_element(int count) 
    { 
        int middle = count/2;
        Node temp = head;
        while(middle>0)
        {
            -- middle;
            temp = temp.next;
        }
        System.out.println("The middle element is " + temp.data ); 
    } 
    public void add(int data) 
    { 
        Node new_node = new Node(data);
        new_node.next = head; 
        head = new_node; 
    } 
    public void print_list() 
    { 
        Node temp = head; 
        while (temp != null) 
        { 
            System.out.print(temp.data+"->"); 
            temp = temp.next; 
        } 
        System.out.println("NULL"); 
    } 
    public static void main(String [] args) 
    { 
        LinkedList list = new LinkedList(); 
        for (int i=0; i<=10; i++) 
        { 
            list.add(i); 
            list.print_list(); 
            int count = count();
            list.middle_element(count); 
        } 
    } 
}

Approach 2: Using one traversal: Slow and fast pointers

The idea is to use two pointers: one pointer (say P1) will move by one step and the other pointer (say P2) will move by two steps.

The middle element will be the element at the first pointer P1 when the second pointer P2 reaches the end of the list.

Pseudocode

The pseudocode of the algorithm to find the middle element using one traversal is as follows:


// one traversal
int middle_element(Node head)
{
    Node first_node = head, second_node = head;
    
    if(head == null) return;
    
    while(first_node != null && second_node != null)
    {
        first_node = first_node.next;
        second_node = second_node.next;
    }
}

Complexity

Worst case time complexity: Θ(N)
Average case time complexity: Θ(N)
Best case time complexity: Θ(N)
Space complexity: Θ(1)

Implementations

Java

Java


class LinkedList 
{ 
    Node head; // head of linked list 
    private class Node 
    { 
        int data; 
        Node next;
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
    void middle_element() 
    { 
        Node pointer_1 = head; 
        Node pointer_2 = head; 
        if(head == null) return;
        while (pointer_2 != null && pointer_2.next != null) 
        { 
            pointer_2 = pointer_2.next.next; 
            pointer_1 = pointer_1.next; 
        } 
        System.out.println("The middle element is " + pointer_1.data ); 
    } 
    public void add(int data) 
    { 
        Node new_node = new Node(data);
        new_node.next = head; 
        head = new_node; 
    } 
    public void print_list() 
    { 
        Node temp = head; 
        while (temp != null) 
        { 
            System.out.print(temp.data+"->"); 
            temp = temp.next; 
        } 
        System.out.println("NULL"); 
    } 
    public static void main(String [] args) 
    { 
        LinkedList list = new LinkedList(); 
        for (int i=0; i<=10; i++) 
        { 
            list.add(i); 
            list.print_list(); 
            list.middle_element(); 
        } 
    } 
}