# How to Find Middle Element of Linked List in Java in One Pass in Java

As if you think carefully you can solve this problem by using two pointers as mentioned in my last post on How to find length of Singly Linked List in Java. By using two pointers, incrementing one at each iteration and other at every second iteration. When first pointer will point at end of Linked List, second pointer will be pointing at middle node of Linked List.

In fact this two pointer approach can solve multiple similar problems e.g. How to find 3rd element from last in a Linked List in one Iteration or How to find nth element from last in a Linked List. In this Java programming tutorial we will see a Java program which finds middle element of Linked List in one Iteration.

## Java program to find middle element of LinkedList in one pass

/**
* Java program to find middle element of linked list in one pass.
* In order to find middle element of linked list we need to find length first
* but since we can only traverse linked list one time, we will use two pointers
* one which we will increment on each iteration while other which will be
* incremented every second iteration. so when first pointer will point to the
* end of linked list, second will be pointing to the middle element of linked list
* @author
*/

public static void main(String args[]) {

//finding middle element of LinkedList in single pass
int length = 0;

while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}

if(length%2 == 1){
middle = middle.next();
}

System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);

}

}

private Node tail;

}

}

tail.next = node;
tail = node;
}

public static class Node{
private Node next;
private String data;

public Node(String data){
this.data = data;
}

public String data() {
return data;
}

public void setData(String data) {
this.data = data;
}

public Node next() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public String toString(){
return this.data;
}
}
}

Output:
middle element of LinkedList : 2

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz

That’s all on How to find middle element of LinkedList in one pass. As I said this is a good interview question to separate programmers from non programmers. Also technique mentioned here to find middle node of LinkedList can be used to find 3rd element from Last  or nth element from last in a LinkedList as well.

Other Java programming tutorials from Javarevisited blog

Pio Jac said...

Maybe my mind is still not awaken after Christmas laziness, but... does this code really return middle element? I think it returns last element with even index. In this code it is solved like you were incrementing index every second time. If you update reference to current every second time, nothing good will come out of this. I'd set middle = middle.next() in loop and also ... initialize length as 0 (I don't consider head element as real element of the list (length should return number of elements carrying data). Greetings!

Javin Paul said...

@Pio Jac, you are right if we don't consider head as real element. In that case initialing length with 0 make sense. Also In order to handle odd length e.g. 3, 5 or 7 where middle element is not updated, we need to handle once loop finished. I have updated code. Thanks for pointing out, it seems, its me, who has Christmas laziness :)

Anonymous said...

Can you please write code for How to find 3rd element from last in Singular Linked List, I didn't get your point on saying that same technique can be used to find Nth element from last in singly linked list. Sorry.

Liu Jin said...

I was asked to find middle item in a linked list in single pass and when I asked what is length of linked list they say, you need to find that as well. I didn't thought that I can use two pointers or two variables to keep track of middle and last item, something I missed. By the way What is big O for best case and worst case for this solution ?

Anonymous said...

In what aspect does this separate the programmers from nonprogrammers, even when you yourself didn't elaborate a complete algorithm?
What is a programmer and what is a nonprogrammer?

Javin @ JDBC Best practices said...

@Anonymous, aspect here is coding, converting logic to code. algorithm here is simple where one pointer is incremented on each iteration, while other is incremented in every second iteration. let me know which part you didn't understand.

Ken Whitesell said...

Actually, I would dispute the assertion that this is being done "in one pass". You're making two separate passes through the list - it's just that you're doing them concurrently and not consecutively.

Anonymous said...

instead of checking length why not you just increment one pointer twice and other pointer only one. this would make your linked list middle element checking code simpler.

Guido Diepen said...

I have to agree with Ken, you just just do two traversals within one loop.

Javin @ prime number in Java said...

@Guido, Can you please elaborate? I think node.next() doesn't traverse the list it just like incrementing pointer, don't agree?

Guido Diepen said...

@Javin: I understand it just increments the pointer.

But as far as I can see, the code keeps track of two elements (i.e. pointers) in the loop: middle and current.

So even though it is executed within one for-loop, I do see two traversals:
* current looping all the way till the end
* middle looping till the middle

That is why I agreed with the statement of Ken that I would not call this one pass. Could just be a word thing and that with one-pass here it is meant you are only allowed to use one for-loop.

Anonymous said...

Ken and Guido.. Good Catch.. I had the same question when I read the article. As you said, if it is a wording issue(like using one for-loop), it clears my doubt.

- Durai

rakeshudandakar said...

Hi,

The simple way to find the middle element is written below

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator;
import javax.xml.soap.Node;
public class test2 {

public static void main(String args[])
{

java.util.Iterator i1=l.iterator();
java.util.Iterator i2=l.iterator();

int i=0;
int middle = 0;
while(i1.hasNext())
{
if(i==0)
{
i1.next();
i=1;

}
else if(i==1)
{
if(i1.hasNext())
{

i1.next();

middle=(Integer) i2.next();
i=0;
}
}
}
System.out.println("middle"+middle);

}

}

Anonymous said...

This extra code:
if(length%2 == 1){
middle = middle.next();
}
is not required..because your code to find middle element will give the same result without this piece of code anyway

Dan Kroll said...

Ken is correct. Unless I am missing something, this isn't one pass, it is 1.5. If you demand an answer for a single pass, a student should respond that it isn't possible and that only 1.5 is possible. The idea that answering this 'incorrectly' could have cost someone a job is slightly disconcerting.

Anonymous said...

Guys please comment on my approach, I am also doing in 1.5 pass. Please suggest if it is efficient or can be improved ?

package my.data.structures;

class LlNode{
int data;
LlNode next;
LlNode prev;
}
LlNode start;
{
start = null;
}

public void insertLl(int d){
LlNode node = new LlNode();
node.data = d;
if (start == null)
{
start = node;
start.next = null;
start.prev = null;
}
else{
LlNode current;
LlNode previous;
current = start;
while(true){
previous = current;
if(current.next==null)
{
current.next = node;
node.prev = previous;
node.next = null;
return;
}
else{
current = current.next;
}
}
}
}

public void displayLl(){
LlNode current;
current = start;
while(current != null){
System.out.print(current.data+"---->");
current = current.next;
}
}

public void findmid() {
// TODO Auto-generated method stub
LlNode current;
LlNode mid;
current = start;
mid = start;
int midnode, i,j;
midnode = 1;
int cur;
cur = 0;
i=0;j=0;
while(current != null){
if(cur==1)
{
System.out.println("\nMid Node is at : "+midnode);
return;
}
else{
mid = mid.next;
midnode++;
for (i=0;i<2;i++){
if(current.next == null){
System.out.println("No mid, length is even");
return;
}
current = current.next;
}
if(current.next == null){
cur=1;
}
}

}

}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
l.insertLl(1);
l.insertLl(2);
l.insertLl(3);
l.insertLl(4);
l.insertLl(5);
l.insertLl(6);
l.insertLl(7);
l.displayLl();
l.findmid();

}

}

Anonymous said...

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

float len = (float) node.size();
float midInd = 0 ;

if(obj.evenOdd(len))
{
midInd= len/2;
}else
{
midInd = (float) ((len/2)- 0.5);
}

int j = (int)midInd;
j = node.get(j);
System.out.print(midInd + " "+j);
}

public boolean evenOdd(float i)
{
if ( i % 2 == 0 )
{
return true;
}else
{
return false;
}

}

}

Anonymous said...

The solution presented here obviously does more than one pass and hence isn't valid. It doesn't matter if all you do is chasing the pointers. You are still traversing 1.5 times and could just as well do a count run and then stop in the middle for the next one with the same effort.

A java LinkedList is a doubly linked list (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html) so the whole premise that you would be working on a singly linked list is wrong too. The correct solution would be to advance from both sides (front and back) of the doubly linked list simultaneously until you meet in the middle element (happens for uneven list length) or the next element matches the current element of the other (happens for even list lengths).

Anonymous said...

public void middle(){
node slow=start.next;
node fast=start.next;
while(fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}

System.out.println(slow.data);
}

10->9->8->7->6->5->4->3->2->1->

5

Anup said...

if(length%2 == 1){
middle = middle.next();
}

Code is not required.
It works without that irrespective of even or odd number of nodes.

Vishwanath Gulabal said...

THIS IS IN C
================================================================================

//C PROGRAM FOR PRINTING THE MIDDLE ELEMENT OF THE LIST

#include
#include
struct node
{
int data;
};
typedef struct node *NODE;
NODE getnode()
{
NODE X;
X=(NODE)malloc(sizeof(struct node));
if(X==NULL)
{
printf("NO NODES TO BE CREATED \n");
exit(0);
}
return X;
}
NODE insert(NODE root,int item)
{
NODE temp=getnode();
temp->data = item;
return temp;
}
NODE display(NODE root)
{
NODE temp=root;
while(temp!=NULL)
{
printf("%d-->",temp->data);
}
}
void middle(NODE root)
{
NODE cur,prev;
if(root==NULL)
{
printf("NO NODES TO BE DISPALYED \n");
}
else
{
prev=root;
cur=root;
{
}
printf("THE MIDDLE ELEMENT IS %d \n",prev->data);
}
}
int main()
{
NODE root;
int item,ch;
while(1)
{
printf("1:INSERT 2:DISPLAY 3:MIDDLE 4:EXIT \n");
printf("ENTER UR CHOICE \n");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("ENTER THE ITEM U WANT TO INSERT \n");
scanf("%d",&item);
root=insert(root,item);
break;
case 2:display(root);
break;
case 3:middle(root);
break;
case 4:exit(0);
break;
}
}
}
==============================================================================

pavan said...

simple way to display middle element

System.out.println(llTest);
System.out.println("size:"+(llTest.size()));

Javin Paul said...

@pavan, linked list doesn't allow random access. You can cannot get element by calling get(index). This is true for our own linked list implementation and also for java.util.LinkedList, which is a doubly linked list.

Abhishek singh said...

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scn = new Scanner(System.in);
System.out.println("How many numbers you want to add");
int n = scn.nextInt();
System.out.println("Start the element to enter in list");
for(int c= 0 ; c <n ; c++ ){
int s = scn.nextInt();
}
System.out.println(n/2);
System.out.println(first);
}

AT said...

// I assume we can remove first and remove last element in a loop
String mid = null;
while (list.peekFirst() != null) {
mid = list.removeFirst();
if (list.peekLast() == null) {
return mid;
}
list.removeLast();
}
return mid;
}

AT said...

// Below there is only one pass, using one ListIterator from head, one desendingIterator from tail
public static String findMid2(LinkedList list) {
ListIterator iter1 = list.listIterator(0);
Iterator iter2 = list.descendingIterator();
String fromTail = null;
while (iter1.hasNext()) {
return iter2.next();
}
fromTail = iter2.next();
}
}
}

Huy Le said...

Hi, my first Java. How to find middle element of LinkedList in one pass.
Iterator iterates through the LinkedList always starts at Z.size()/2. The "count" speaks it all.

class Numbers {
int N;
Numbers (int R) { N = R;}
public String toString() { return "" + N; }
}

public class FindMiddle {
public static void main(String[] args) {

print(Z.toString()); print(Z.size());

ListIterator it = Z.listIterator(Z.size()/2);
int count = 0;
while( it.hasNext()) {
it.next();
++count;
}
print(count);

}
}
/*OUTPUT
[1, 2, 9, 4, 5, 6, 7, 999, 999]
9
count is:5
*/

Javin Paul said...

@Huy, good solution, try writing some JUnit tests as well to see if your program works on boundary conditions e.g. linked list with even number of elements, odd number of elements etc.

Unknown said...

/**
*Find below code for finding the middle element by two pointer method
*/

Node nod1 = list;
Node nod2 = list;
while (nod2.next != null) {
if (nod2.next != null)
nod2 = nod2.next;
else
nod1 = nod1.next;
if (nod2.next != null)
nod2 = nod2.next;
else
nod1 = nod1.next;
}
System.out.println("middle by two pointer increment : " + nod1.value);

Huy Le said...

Hi jarvin, here's your request. find odd and even numbers in the list

class Numbers {
int N;
Numbers (int R) { N = R;}
public String toString() { return "" + N; }
int getValue() { return N; }
}

public class FindMiddle {
public static void main(String[] args) {

print(Z.toString()); print(Z.size());

ListIterator it = Z.listIterator();

int b;
if ( it.hasNext()) {
it.next();
for ( int i = 0; i < Z.size(); i++) {
b = Z.get(i).getValue();
if ( b % 2 == 0) {
print(b);
}
else
print(b);
}

}
}
}
/*OUTPUT
[100, 200, 300, 400, 500, 600, 700, 800, 999, 9999, 99999999, 99999999]
12
100
200
300
400
500
600
700
800
999
9999
99999999
99999999
*/

Javin Paul said...

@Huy, Thanks for your code, but I think I suggested to write JUnit tests for your code to verify if the solution works for a linked list with even number of elements and a list with odd number of elements e.g. linked list with 5 elements.

nevermind, good practice anyway.

Joshua Frost said...

I have to be honest.... this is a nice solution and all but...the real answer is there is no way of completing this with a single pass. Two pointers means you are making two passes. This is the same for all of the implementations I have seen. I think others have echoed the same sentimate and I realize that at some point this could come down to a wording issue. This is not a slight against the author of it - it is more of an annoyance with these types of questions meant to "weed out programmers from none" because we are fabricating solutions that aren't really solutions. Words mean something, one pass is one pass and the first pass is done by the time the second pointer ever has a chance.

Javin Paul said...

@Joshua, you may be right. I guess the pass initially refer to how many loop you use to find the middle element of linked list, but you are right, it's not the correct word. A pass can also means accessing the linked list twice.

Akanksha Jain said...

I wrote this function to find the middle element. I am getting the results:
public void middleElement(){
int length = 0;
while(current.next!=null){
length++;
if(length%2==0){
middle = middle.next;
}
current = current.next;
if(length%2 == 1){
current = current.next;
}
}
middle = middle.next;
System.out.println(middle.data);
}

Anonymous said...

Guys let me know if i am wrong but i think following code will give us what we want(assuming the list is even)??.

int p = 0;

p =(l.indexOf(l.getLast()))/2 ;

System.out.println(l.get(p));

Anonymous said...

what about ArrayList ? if you add all nodes to ArrayList while traversing you solve indexed search and any search question if there is no cycle there . right ?

p.s.: why can't I comment using facebook ?

Aslam Anwer said...

As many have pointed out as this answer is looks not correct. I am agreeing with them.
Please change the title of the quesion @Author, @Javin Paul.
Its not one pass it is 1.5 pass

Yasin Hamid said...

I am bit puzzled about this problem and solution. Why did you create your own implementation of LinkedList? I would assume that the question was about java.util.LinkedList. If memory is not an issue than creating an Array from LinkedList would be one pass and much simpler.