如何在单次遍历中找到Python链表中的中间元素？

Question

很抱歉提出这样的问题（编程新手）：

我想用findMid方法找到链表的中间元素。很抱歉解释不清楚，因为英语不是我的母语。谢谢：）

我的代码正在创建链表，我想通过一次遍历找到链表的中间元素。到目前为止，我通过向google寻求帮助，实现了一个使用指针概念的函数，该函数是：

def findMid(self):
    slowPtr = self.__head
    fastPtr = self.__head
    if not self.__head is not None:
        while fastPtr is not None and fastPtr.next is not None:
            fastPtr = fastPtr.next.next
            slowPtr = slowPtr.next
        return slowPtr

但它给我的回报是

我剩下的链表代码是：

^{pr2}$

Answer 1

要在一次单次过程中找到中间的数字，您需要为长度保留一个计数器，并存储所看到的元素的完整列表。然后，可以通过flattened_results[counter//2]找到中间的数字：

class Link:
  def __init__(self, head = None):
     self.head = head
     self._next = None
  def insert_node(self, _val):
     if self.head is None:
       self.head = _val
     else:
       if self._next is None:
         self._next = Link(_val)
       else:
         self._next.insert_node(_val)
  def traverse(self, count = 0):
    yield self.head
    if not self._next:
      yield [count]
    else: 
      yield from self._next.traverse(count+1)
  @classmethod
  def load_list(cls, num = 10):
     _list = cls()
     import random
     for i in range(num):
        _list.insert_node(random.choice(range(1, 20)))
     return _list

t = Link.load_list()
*l, [count] = list(t.traverse())
print(f'full list: {l}')
print('middle value:', l[count//2])

输出：

^{pr2}$