How could this doubly linked list search code be implemented?

Question

I got this code which is supposed to provide an algorithm that searches for the item in the middle of a doubly-linked list. There may be one or more flaws in the code making the code not executable. How can this code be implemented to make it work using a linked list? And what are the problems in the code itself?

node1 = self.head
node2 = self.tail

while node1 != node2: 
    node1 = node1.next
    node2 = node2.previous
return node1.value

Answer 1

The problem is you 'step' both nodes at the same time inside the loop. You can thus miss the middle because they can jump over each other without being detected.

You should step one node at a time in each loop iteration. The solution could be something like this:

node1 = self.head
node2 = self.tail

step_node_1 = True
while node1 != node2:
    if step_node_1:
        node1 = node1.next
        step_node_1 = False
    else:
        node2 = node2.previous
        step_node_1 = True

return node1.value