python - 在 Python 中，给定一个单链表，通过将其分成两半（围绕中位数）折叠它并反转每一半

Question

我可以扭转它，但对如何访问链表的中位数感到困惑

def reverseLinkedList(head):

    current =  head
    previous = None
    nextNode = None

    while current:
        nextNode = current.nextNode
        current.nextNode = previous

        previous = current
        current = nextNode

    return previous

有人可以帮忙解决吗？

标签： pythonreverse

Answer 1

链表不支持随机访问。因此，除非您提前知道链表中的元素数量或中间节点通过代码中的节点结构/定义被标记为这样，否则您将无法在不迭代的情况下获得它。

如果您知道链表中元素的数量，您可以只迭代其中的一半，否则您将不得不迭代整个列表，跟踪计数，然后再次迭代以计数除以 2。