Trusted answers to developer questions
How to find the mid of a singly linked list in a single traversal
Ravi
Overview
Given a singly linked list, find the middle node/element of the list in a single traversal.
Example 1:
- Input -
1 -> 2 -> 3 -> 4 -> 5 - Output -
3
Example 2:
- Input -
1 -> 2 -> 3 -> 4 - Output -
3
If the list contains an even number of nodes, two elements can be the middle elements. The second middle element has to be considered as the middle element. In Example 2, 2 and 3 can both be middle elements, but 3 should be considered as the middle element.
Solution
This problem can be solved using two pointers that are initially pointing to the head node. Let’s name the two pointers as slow_ptr and fast_ptr.
The steps of the algorithm are as follows:
- Initialize
slow_ptrandfast_ptrto the head node. - Continue performing the following steps until the
fast_ptror the next element offast_ptrreaches the end of the list:- Move the
slow_ptrby one node. - Move the
fast_ptrby two nodes.
- Move the
By the time fast_ptr reaches the end of the list, slow_ptr will be pointing to the middle node of the list.
- Time complexity:
O(N) - Space complexity:
O(1)
Example
public class Main{
static class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
static class SLL{
Node head;
public SLL() {
this.head = null;
}
public void pushFront(int data){
Node node = new Node(data);
node.next = head;
head = node;
}
public void print(){
Node temp = head;
while(temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}
public void getMiddle(){
if(head == null) {
System.out.println("Empty list. Cannot get the middle node");
return;
}
Node slowPtr = head;
Node fastPtr = head;
while(fastPtr != null && fastPtr.next != null){
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}
System.out.println("The middle element is - " + slowPtr.data);
}
}
public static void main(String[] args) {
SLL sll = new SLL();
sll.pushFront(5);
sll.pushFront(4);
sll.pushFront(3);
sll.pushFront(2);
System.out.println("Even number of nodes list:");
sll.print();
sll.getMiddle();
System.out.println("----");
System.out.println("Odd number of nodes list:");
sll.pushFront(1);
sll.print();
sll.getMiddle();
}
}Mid of SLL in Java
RELATED TAGS
java
CONTRIBUTOR
Ravi
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
