0
$\begingroup$

Is there a way possible to find the middle element of a doubly linked list using head and tail. I tried traversing to the next element from the starting node and the previous element from the end node and check if the reference of both is same or not. This works fine if there are odd number of elements in the list. I am not able to find when should I stop in case the number of elements in the list is even.

while(head.next != end.previous) {
    head = head.next;
    end = end.previous;
}
$\endgroup$
3
  • $\begingroup$ What does it mean to find the middle element "in $n/2$"? What are you counting here? $\endgroup$ Apr 17 '18 at 8:44
  • $\begingroup$ I meant n/2 iterations. $\endgroup$ Apr 17 '18 at 8:45
  • $\begingroup$ What does "iteration" constitute? Otherwise it's hard to argue one way or another. $\endgroup$ Apr 17 '18 at 8:46
2
$\begingroup$

Start with a pointer $x$ at the beginning and a pointer $y$ at the end. Repeatedly execute the following steps:

  • If $x=y$, stop.
  • Advance $x$ forward.
  • If $x=y$, stop.
  • Advance $y$ backward.

This should work out for both even and odd length.

$\endgroup$
3
  • $\begingroup$ But we cannot avoid two comparisons? $\endgroup$ Apr 17 '18 at 8:41
  • 1
    $\begingroup$ You don't need comparisons at all. You can calculate the length of the list, and then go straight to the middle element. $\endgroup$ Apr 17 '18 at 8:45
  • $\begingroup$ Yes, I can. There are other ways too like using 2 pointers. One which points next->next and one which points next. When the first pointer reaches the end, the second will be at mid. I was just curious if we can do it with the way I am working. $\endgroup$ Apr 17 '18 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.