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

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.

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

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

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.

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.

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

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)

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.