Start networking and exchanging professional insights

Register now or log in to join your professional community.

Follow

How do you find middle element of a linked list in single pass?

user-image
Question added by Lia Madanat , Senior Programmer , InspireJO
Date Posted: 2017/05/16

you can create two pointers; slow and fast 

slow once moves 1 step at a time and the fast once moves 2

always check if fast can move forward (e.g., if not null) before moving it

if it cannot move then it's the end 

now slow pointer is in the exact middle of your linked list.

Mohammad shamim Akhter khan
by Mohammad shamim Akhter khan , Project Lead , Jharkhand

If it's not a doubly linked list, you could just count and use a list, but that requires doubling your memory in the worst case, and it simply won't work if the list is too large to store in memory.

 

A simple, almost silly solution, is just increment the middle node every two nodes

 

function middle(start) {

    var middle = start

    var nextnode = start

    var do_increment = false;

    while (nextnode.next != null) {

        if (do_increment) {

             middle = middle.next;

        }

        do_increment = !do_increment;

        nextnode = nextnode.next;

    }

    return middle;

}

Programminfg is the acto or crating computer programm

Bhavadharini Vadamalaipalayam Govindaraj
by Bhavadharini Vadamalaipalayam Govindaraj , Senior Software Engineer , Infosys

Method 1 : When list size is unknown:

  • When the size of the list is unknown, we need to traverse the list to find the middle element. 
  • This can done by using 2 pointers, Initially both the pointers will be pointing to the first element of the list
  • Using a while loop , for each iteration,  The first pointer moves 2 steps ahead and  the second pointer moves 1 step
  • when the first pionter reaches the end, the second pointer would be pointing to the middle element
  • For example , Take a list with elements 1,2,3,4,5 
    • While First pointer.next() != null
    • 1st Iteration - 2nd Pointer: 1, 1st Poniter : 1
    • 2nd Iteration - 2nd Pointer: 2, 1st Poniter : 3
    • 3rd Iteration -  2nd Pointer: 3, 1st Poniter : 5
    • since first poniter has reached the end, no. that is in 2nd poniter is middle element

Method 2 : When list size is known:

If you can find the list size using java inbuilt methods , then all you have to do is find the of listLength/2 and get the number in that index position

uday alkazzaz
by uday alkazzaz , Research assistant , Communications Network Research Institute

They don't want you to come with algorithm O(n), because both of them has O(n) complexity. Common person will say, there's no way to know where is middle if i don't traverse once (so traversing once to find length, and traversing 2nd time to find middle is two passes for those who interview you). They want you to think outside of box, and figure out way you mentioned which include two pointers.

So the complexity is same, but the way of thinking is different, and people who interview you want to see that.

Qasim Parray
by Qasim Parray , Full Stack Developer , SellAnything365

We have to maintain 2 pointers, a center, and current. And to increment the center pointer when the number of elements encountered is divisible by 2.

Abdelrahman AlMhisen
by Abdelrahman AlMhisen , Research & Development Manager , Menacast

Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

by traversal we get the total number of elements and the value is then divided by 2

By using front ant head of each element

Mohammad Ahmed
by Mohammad Ahmed , Senior Solutions Consultant , OmarAzam Saudi Consultancy

In Object oriented programming,

lnlist.size() will give us the current length of the list which could be zero, one, even number or odd number

lnlist.get(((even length)/2) -1)

lnlist.get(((odd length + 1)/2) -1)

Jonathan de Flaugergues
by Jonathan de Flaugergues , software engineer , Abbeal

You can solve it with one pointer to be traversing one element at a time, while the second pointer moves 2 elements at a time.This way when the second pointer reaches the end, the first pointer will be at the middle.

More Questions Like This

Do you need help in adding the right keywords to your CV? Let our CV writing experts help you.