Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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:
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();
}
}
}
