这个双向链表搜索代码是如何实现的？

Question

我得到了这段代码，它应该提供一种算法来搜索双向链表中间的项目。代码中可能存在一个或多个缺陷，导致代码无法执行。如何实现此代码以使其使用链表工作？以及代码本身存在哪些问题？

node1 = self.head
node2 = self.tail

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

Answer 1

问题是你 'step' 两个节点同时在循环中。因此，您可能会错过中间部分，因为它们可以在不被发现的情况下相互跳过。

您应该在每次循环迭代中一次单步执行一个节点。解决方案可能是这样的：

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

Answer 2

what are the problems in the code itself?

存在这些问题：

可能很明显，但代码必须放在函数中，否则return是语法错误。此外，由于有对self的引用，这表明函数是链表class.
的方法
如果列表为空，则 node1 和 node2 将是 None。当执行node1.value时，会出现异常。你需要妥善处理空列表的情况
如果列表的节点数为偶数（且不为空），则node1和node2将相互走过，并继续直到到达列表的另一端变为 None。然后将再次发生与上述相同的异常。您还可以通过检查 node1 和 node2 是（不是）邻居来解决这个问题

这里是代码的更正和补全：

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt
        self.previous = None

class LinkedList:
    def __init__(self):
        self.head = self.tail = None

    def push_front(self, value):
        self.head = Node(value, self.head)
        if self.tail:
            self.head.next.previous = self.head
        else:
            self.tail = self.head

    def get_mid_value(self):
        node1 = self.head
        node2 = self.tail

        while node1 != node2 and node1.next != node2:  # Neighbor check
            node1 = node1.next
            node2 = node2.previous
    
        if node1:  # Guard
            return node1.value

# Demo
lst = LinkedList()
lst.push_front(2)
lst.push_front(1)
print(lst.get_mid_value())

Answer 3

如果列表为空，self.head 和 self.tail 将是 None。在最后一行你会 return None.value 这会导致错误。看看这个例子：列表有 4 个节点 n1、n2、n3、n4

循环前

node1 = n1, node2 = n4

迭代

node1 = n2, node2 = n3

迭代

node1 = n3, node2 = n2

node1 和 node2 不相同，即使它们指向中间元素。循环连续

迭代

node1 = n4, node2 = n1

迭代

node1 = None, node2 = None

最后 node1 和 node2 相同，因此循环中断。然后因为 node1 等于 None return None.value 将被调用而导致错误。您的代码应如下所示：

node1 = self.head
node2 = self.tail
    
while node1 != node2 and node1.next != node2: 
    node1 = node1.next
    node2 = node2.previous
        
if node1 != None: return node1.value

这个双向链表搜索代码是如何实现的？

How could this doubly linked list search code be implemented?

python

doubly-linked-list