×

Search anything:

# Find the middle element of a singly Linked List 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:

### 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 = 0;

while(temp.next != null)
{
++ count;
temp = temp.next;
}
return count;
}

// second traversal
{
int middle = (int)count/2;

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)`

• Java

### Java

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

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)`

• Java

### Java

``````
{
private class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void middle_element()
{
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 );
}
{
Node new_node = new Node(data);
}
public void print_list()
{
while (temp != null)
{
System.out.print(temp.data+"->");
temp = temp.next;
}
System.out.println("NULL");
}
public static void main(String [] args)
{
for (int i=0; i<=10; i++)
{
list.print_list();
list.middle_element();
}
}
}
`````` #### OpenGenus Tech Review Team

The official account of OpenGenus's Technical Review Team. This team review all technical articles and incorporates peer feedback. The team consist of experts in the leading domains of Computing.

Improved & Reviewed by:

Find the middle element of a singly Linked List