Related Tags

java

# 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:

1. Initialize slow_ptr and fast_ptr to the head node.
2. Continue performing the following steps until the fast_ptr or the next element of fast_ptr reaches the end of the list:
1. Move the slow_ptr by one node.
2. Move the fast_ptr by two nodes.

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{

public SLL() {
}

public void pushFront(int data){
Node node = new Node(data);
}

public void print(){
while(temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}

public void getMiddle(){
System.out.println("Empty list. Cannot get the middle node");
return;
}

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

Learn in-demand tech skills in half the time 