ابدأ بالتواصل مع الأشخاص وتبادل معارفك المهنية

أنشئ حسابًا أو سجّل الدخول للانضمام إلى مجتمعك المهني.

متابعة

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

user-image
تم إضافة السؤال من قبل Lia Madanat , Senior Programmer , InspireJO
تاريخ النشر: 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
من قبل Mohammad shamim Akhter khan , Senior software developer , Easey trip planner LTD

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;

}

Muhammad Hasan
من قبل Muhammad Hasan

Programminfg is the acto or crating computer programm

Bhavadharini Vadamalaipalayam Govindaraj
من قبل 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
من قبل uday alkazzaz , director Manager / Engineer , ultraComputers

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
من قبل 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
من قبل 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.

Jemy Sam
من قبل Jemy Sam

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

Mohammad Ahmed
من قبل 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
من قبل 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.

المزيد من الأسئلة المماثلة