أنشئ حسابًا أو سجّل الدخول للانضمام إلى مجتمعك المهني.
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:
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.