ow do you find the middle element of LinkedList in one pass is a programming question often asked Java and non-Java programmers in telephonic Interview. This question is similar to checking palindrome or calculating the factorial, where Interviewer sometimes also ask to write code. In order to answer this question candidate must be familiar with LinkedList data structure i.e. In the case of singly LinkedList, each node of Linked List contains data and pointer, which is the address of next Linked List and the last element of Singly Linked List points towards the null. Since in order to find middle element of Linked List you need to find the length of linked list, which is counting elements till end i.e. until you find the last element of Linked List.

What makes this data structure Interview question interesting is that you need to

This is where candidates logical ability puts into the test, whether he is familiar with space and time trade-off or not etc.

As if you think carefully you can solve this problem by using two pointers as mentioned in my last post on How to find the length of the Singly Linked List in Java.

By using two pointers, incrementing one at each iteration and other at every second iteration. When the first pointer will point at end of Linked List, the second pointer will be pointing at a middle node of Linked List.

In fact, this two pointer approach can solve multiple similar problems like how to find the third node from last in a Linked List in one Iteration or how to find an Nth element from last in a Linked List. In this Java programming tutorial, we will see a Java program which finds the middle element of Linked List in one Iteration.

What makes this data structure Interview question interesting is that you need to

*find the middle element of**LinkedList**in one pass*and you don’t know the length of LinkedList.This is where candidates logical ability puts into the test, whether he is familiar with space and time trade-off or not etc.

As if you think carefully you can solve this problem by using two pointers as mentioned in my last post on How to find the length of the Singly Linked List in Java.

By using two pointers, incrementing one at each iteration and other at every second iteration. When the first pointer will point at end of Linked List, the second pointer will be pointing at a middle node of Linked List.

In fact, this two pointer approach can solve multiple similar problems like how to find the third node from last in a Linked List in one Iteration or how to find an Nth element from last in a Linked List. In this Java programming tutorial, we will see a Java program which finds the middle element of Linked List in one Iteration.

Btw, if you are new to Algorithms and Data Structure and not familiar with essential data structure like linked list, array or binary tree then I suggest you go through a good, comprehensive online course like

**Data Structures and Algorithms: Deep Dive Using Java**to learn the basics and brush up the fundamentals.

##
__How to Find Middle Element of LinkedList in One Pass__

Here is a complete Java program to find the middle node of Linked List in Java. Remember LinkedList class here is our custom class and don’t confuse this class with java.util.LinkedList which is a popular Collection class in Java.

In this Java program, our class LinkedList represent a linked list data structure which contains a collection of the node and has head and tail.

Each node contains data and addresses part. The main method of LinkedListTest class is used to simulate the problem, where we created Linked List and added few elements on it and then iterate over them to find middle element of linked list in one pass in Java.

If you want to learn more about linked list data structure and different types of linked lists like a singly linked list, doubly linked list, circularly linked list et all then you can also check the

Btw, you would need a Pluralsight membership to access this course. If you are not a member, you can still access this course by using the 10-day free pass provided by Pluralsight to explorer its portal and online courses.

In this Java program, our class LinkedList represent a linked list data structure which contains a collection of the node and has head and tail.

Each node contains data and addresses part. The main method of LinkedListTest class is used to simulate the problem, where we created Linked List and added few elements on it and then iterate over them to find middle element of linked list in one pass in Java.

If you want to learn more about linked list data structure and different types of linked lists like a singly linked list, doubly linked list, circularly linked list et all then you can also check the

**Algorithms and Data Structures - Part 1 and 2**courses on Pluralsight. One of the better courese to learn data structure and algorithms.Btw, you would need a Pluralsight membership to access this course. If you are not a member, you can still access this course by using the 10-day free pass provided by Pluralsight to explorer its portal and online courses.

###
__Java Program to Find the Middle Node of a Linked list in a Single-pass__

__Java Program to Find the Middle Node of a Linked list in a Single-pass__

**import**test.LinkedList.Node;

/**

*

**Java program to find middle element of linked list in one pass**.

* In order to find middle element of a linked list

* we need to find the length first but since we can only

* traverse linked list one time, we will have to use two pointers

* one which we will increment on each iteration while

* other which will be incremented every second iteration.

* So when the first pointer will point to the end of a

* linked list, second will be pointing to the middle

* element of a linked list

*

* @author Javin Paul

*/

**public**

**class**LinkedListTest {

**public**

**static**

**void**main(

**String**args[]) {

*//creating LinkedList with 5 elements including head*

**LinkedList**linkedList =

**new**

**LinkedList**();

**LinkedList**.

**Node**head = linkedList.head();

linkedList.add(

**new**

**LinkedList**.

**Node**("1"));

linkedList.add(

**new**

**LinkedList**.

**Node**("2"));

linkedList.add(

**new**

**LinkedList**.

**Node**("3"));

linkedList.add(

**new**

**LinkedList**.

**Node**("4"));

*//finding middle element of LinkedList in single pass*

**LinkedList**.

**Node**current = head;

**int**length = 0;

**LinkedList**.

**Node**middle = head;

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

}

}

**class**

**LinkedList**{

**private**

**Node**head;

**private**

**Node**tail;

**public**

**LinkedList**(){

**this**.head =

**new**

**Node**("head");

tail = head;

}

**public**

**Node**head(){

**return**head;

}

**public**

**void**add(

**Node**node){

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

length of LinkedList: 4

middle element of LinkedList: 2

That’s all on

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Introduction to Algorithms by Thomas H. Corman

50+ Data Structure and Algorithms Problems from Interviews

If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :

**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, the technique mentioned here to find middle node of LinkedList can be used to find the 3rd element from Last or nth element from last in a LinkedList as well.**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

Introduction to Algorithms by Thomas H. Corman

50+ Data Structure and Algorithms Problems from Interviews

If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :

- How to check if LinkedList contains any cycle in Java? (solution)
- How to search element in an array in Java? (solution)
- How to sort an array using bubble sort algorithm? (algorithm)
- How to calculate Sum of Digits of a number in Java? (Solution)
- Write a program to find first non repeated characters from String in Java? (program)
- How to check if a number is binary in Java? (answer)
- Write a program to check if a number is Prime or not? (solution)
- How to prevent Deadlock in Java? (solution)
- How to find the largest prime factor of a number in Java? (solution)
- How to calculate a factorial using recursion in Java? (algorithm)
- How to declare and initialize a two-dimensional array in Java? (solution)
- Write a method to count occurrences of a character in String? (Solution)
- How to check if a number is Armstrong number or not? (solution)
- Write a Program remove duplicates from an array without using Collection API? (program)
- How to reverse String in Java without using API methods? (Solution)
- Write a method to remove duplicates from ArrayList in Java? (Solution)
- Write a program to check if a number is a Palindrome or not? (program)
- Write a program to check if the Array contains a duplicate number or not? (Solution)
- How to find the Fibonacci sequence up to a given Number? (solution)
- Write a program to find a missing number in a sorted array? (algorithm)
- 10 Points about Array in Java? (must know facts)
- How to find top two maximum on integer array in Java? (solution)
- Write a method to check if two String are Anagram of each other? (method)
- How to find the largest and smallest number in an array? (solution)
- Write a function to find middle element of linked list in one pass? (solution)
- How to solve the Producer-Consumer Problem in Java. (solution)
- Write a Program to Check if a number is Power of Two or not? (program)

Thanks for reading this coding interview question so far. If you like this String interview question then please share with your friends and colleagues. If you have any question or feedback then please drop a comment.

**P. S.**- If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of**Free Data Structure and Algorithms Courses**for Programmers.
## 50 comments :

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!

@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 :)

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.

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 ?

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?

@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.

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.

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.

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

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

@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.

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

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.LinkedList;

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[])

{

LinkedList l=new LinkedList();

l.add(2);

l.add(3);

l.add(9);

l.add(4);

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

}

}

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

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.

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;

}

class Linked{

LlNode start;

public Linked()

{

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 class LinkedList{

public static void main(String[] args) {

Linked l = new Linked();

// 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();

}

}

import java.util.LinkedList;

public class LinkedListTest {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

LinkedList node = new LinkedList();

node.add(4);

node.add(5);

node.add(7);

node.add(10);

node.add(2);

node.add(1);

node.add(22);

LinkedListTest obj =new LinkedListTest();

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;

}

}

}

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

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

if(length%2 == 1){

middle = middle.next();

}

Code is not required.

It works without that irrespective of even or odd number of nodes.

THIS IS IN C

================================================================================

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

#include

#include

struct node

{

int data;

struct node *link;

};

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;

temp->link=root;

return temp;

}

NODE display(NODE root)

{

NODE temp=root;

while(temp!=NULL)

{

printf("%d-->",temp->data);

temp = temp->link;

}

}

void middle(NODE root)

{

NODE cur,prev;

if(root==NULL)

{

printf("NO NODES TO BE DISPALYED \n");

}

else

{

prev=root;

cur=root;

while(cur->link!=NULL)

{

prev=prev->link;

cur=cur->link->link;

}

if(cur->link==NULL)

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;

}

}

}

==============================================================================

simple way to display middle element

List llTest=new LinkedList();

llTest.add(23);

llTest.add(25);

llTest.add(34);

llTest.add(21);

llTest.add(29);

llTest.add(31);

llTest.add(39);

System.out.println(llTest);

System.out.println(" element of LinkedList is : " + ((LinkedList) llTest).get(llTest.size()/2));

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

@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.

public static void main(String[] args) {

// TODO Auto-generated method stub

LinkedList linked = new LinkedList();

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();

linked.add(c,s);

}

System.out.println(linked);

System.out.println(linked.size());

System.out.println(n/2);

int first = linked.get(n/2);

System.out.println(first);

}

// I assume we can remove first and remove last element in a loop

public static String findMidNodeInLinkedList(final LinkedList list) {

String mid = null;

while (list.peekFirst() != null) {

mid = list.removeFirst();

if (list.peekLast() == null) {

return mid;

}

list.removeLast();

}

return mid;

}

// 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 fromHead = null;

String fromTail = null;

while (iter1.hasNext()) {

fromHead = iter1.next();

if (fromHead == fromTail) {

return iter2.next();

}

fromTail = iter2.next();

if (fromHead == fromTail) {

return fromHead;

}

}

return fromHead;

}

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

LinkedList Z= new LinkedList<>();

Z.add(new Numbers(1)); Z.add(new Numbers(2)); Z.add(new Numbers(3)); Z.add(new Numbers(4)); Z.add(new Numbers(5));

Z.add(new Numbers(6)); Z.add(new Numbers(7)); Z.add(new Numbers(8)); Z.add(new Numbers(999));

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

*/

@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.

/**

*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);

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

LinkedList Z= new LinkedList<>();Z.add(new Numbers(100)); Z.add(new Numbers(200)); Z.add(new Numbers(300)); Z.add(new Numbers(400)); Z.add(new Numbers(500));Z.add(new Numbers(600)); Z.add(new Numbers(700)); Z.add(new Numbers(800)); Z.add(new Numbers(999)); Z.add(new Numbers(9999));Z.add(new Numbers(99999999)); Z.add(new Numbers(99999999));

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

*/

@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.

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.

@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.

I wrote this function to find the middle element. I am getting the results:

public void middleElement(){

int length = 0;

Node middle = head;

Node current = head;

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

}

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;

LinkedList l = new LinkedList();

l.add(0);

l.add(1);

l.add(2);

l.add(3);

l.add(4);

l.add(5);

l.add(6);

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

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

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 ?

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

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.

//Shashikumar J B

public class Middle_Node_Linked_List {

public static void main(String[] args) {

LinkedList Checking = new LinkedList<>();

int[] sample = {40, 20, 60, 10, 50, 30};

//int[] sample = {40, 20, 60};

//int[] sample = {40};

for (int i = 0; i < sample.length; i++) {

Checking.add(sample[i]);

}

int mid = (int) Math.ceil(Checking.size()/2);

System.out.println("size : " + Checking.get(mid));

}

}

@Javin Paul, Why there is extra head when we can consider "1" as head?

In that case, while loop would look like "while(current != null)" instead of "while(current.next() != null)".

Or without extra head, Will it return correct length?

Sorry Guys why cant we use this

public class FindMiddleInList {

public static void main(String[] args) {

// TODO Auto-generated method stub

LinkedList list=new LinkedList<>();

IntStream.range(1,11).forEach(i->list.add(i));

System.out.println(list.get(list.size()/2));

}

}

void middleNode(list_t *head, int *val){

if (!head)

return;

list_t *slow, *fast;

slow=fast=head;

while(fast&&fast->next){

slow=slow->next;

fast=fast->next->next;

}

*val = slow->data;

}

I am just returning the value of the middle node. We could return the node itself. Only catch, need to ask interviewer what if the list is of even number. In that case, there will two middle nodes :-) !!

Easiest way to find the middle element.

https://youtu.be/EsdVJkf2ivI

Perhaps another way of solving this would be using Floyd's slow and fast pointer's concept. Increment the fast pointer by two at each incremental stage until the next of it is not null and increment the slow pointer by one and you shall find the middle element.

Hello @Anonymous, yes, the fast and slow pointer approach should also work but just check with list with even and odd length, may require bit consideration.

package problem.solving.linkedlist.practise;

public class FindMiddleElement{

private Node head;

private Node tail;

private int size = 0;

private class Node{

T data;

Node next;

public Node(T data, Node next){

this.data = data;

this.next = next;

}

}

public int size() {

return size;

}

public boolean isEmpty() {

return size() == 0;

}

public void addLast(T ele) {

if (isEmpty()) {

head = tail = new Node(ele,null);

}else {

tail.next = new Node(ele,null);

tail = tail.next;

}

size++;

}

@Override

public String toString() {

StringBuilder sb = new StringBuilder();

sb.append("[ ");

Node trav = head;

while (trav != null) {

sb.append(trav.data + ", ");

trav = trav.next;

}

sb.append("]");

return sb.toString();

}

public void findMiddleElement() {

Node slowTrav = head;

Node fastTrav = head;

if(isEmpty()) {

throw new RuntimeException("Linked List is empty");

}else {

while(fastTrav != null && fastTrav.next != null) {

fastTrav = fastTrav.next.next;

slowTrav = slowTrav.next;

}

}

System.out.println("Middle Element is : " + slowTrav.data);

}

public static void main(String [] args) {

FindMiddleElement find = new FindMiddleElement();

find.addLast(1);

find.addLast(5);

find.addLast(6);

// find.addLast(8);

// find.addLast(9);

// find.addLast(10);

System.out.println(find.toString());

find.findMiddleElement();

}

}

/**

*How to Find Middle Element of Linked List in Java in Single Pass.

* Works on both even or odd sized linked List

* @Author: Kennedy

*/

import java.util.LinkedList;

public class MiddleElement

{

public static void main(String []args)

{

//Create a linked list

LinkedList object = new LinkedList();

//Add elements to a linked list

object.add(1);

object.add(2);

object.add(3);

object.add(4);

object.add(5);

object.add(6);

object.add(7);

System.out.println("Linked list elements :"+" "+ object);

//get linked list size

int size = object.size();

//print linked lists size

System.out.println("Linked list size is :"+" "+ size);

//get middle of odd sized linked list

if((size % 2) != 0)

{

int middle = ((size - 1)/2);

Object element = object.get(middle);

//print middle element

System.out.println(".....................");

System.out.println("ODD SIZED LINKED LIST");

System.out.println(".....................");

System.out.println("Middle Linked list element is :"+" "+ element);

}

//get two middles of even sized linked list

else

{

//get first middle

int middle1 = (size / 2)-1;

Object element1 = object.get(middle1);

//print first middle element

System.out.println(".....................");

System.out.println("EVEN SIZED LINKED LIST");

System.out.println(".....................");

System.out.println("First middle Linked list element is :"+" "+ element1);

//get second middle

int middle2 = (size / 2);

Object element2 = object.get(middle2);

//print second middle element

System.out.println("Second middle Linked list element is :"+" "+ element2);

}

}

}

/**

OUTPUT 1

..................

Linked list elements : [1, 2, 3, 4, 5, 6, 7]

Linked list size is : 7

.....................

ODD SIZED LINKED LIST

.....................

Middle Linked list element is : 4

OUTPUT 2

..................

Linked list elements : [1, 2, 3, 4, 5, 6]

Linked list size is : 6

.....................

EVEN SIZED LINKED LIST

.....................

First middle Linked list element is : 3

Second middle Linked list element is : 4

*/

Hello Ken, you need to solve this without using LinkedList class, create your own class with ListNode which has data and reference to another ListNode and then create a linked list form that.

Why this method is not one pass?

In this method we are traversing through at most "size of the list" elements.

But in the brute force. You need 1.5*(size of the list).

## Post a Comment