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

Question

很抱歉问这样的问题(编程新手):

我想使用findMid 方法找到链表的中间元素。抱歉解释不当，因为英语不是我的母语。谢谢 :)

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

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

但它返回我 None

我剩下的链表代码是:

 class LinkedList(object):

        class Node(object):
            def __init__(self, element,next=None):
                self.element = element
                self.next = next
                # method returns address of the next Node
        def __init__(self,initial=None):
            self.__head = None
            self.__tail = None
            self.__size = 0
            if initial is not None:
                self.add(initial)

        **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**



        # Return the head element in the list 
        def getFirst(self):
            if self.__size == 0:
                return None
            else:
                return self.__head.element

        # Return the last element in the list 
        def getLast(self):
            if self.__size == 0:
                return None
            else:
                return self.__tail.element

        # Add an element to the beginning of the list 
        def addFirst(self, e):
            newNode = self.Node(e) # Create a new node
            newNode.next = self.__head # link the new node with the head
            self.__head = newNode # head points to the new node
            self.__size += 1 # Increase list size

            if self.__tail == None: # the new node is the only node in list
                self.__tail = self.__head

        # Add an element to the end of the list 
        def addLast(self, e):
            newNode = self.Node(e) # Create a new node for e

            if self.__tail == None:
                self.__head = self.__tail = newNode # The only node in list
            else:
                self.__tail.next = newNode # Link the new with the last node
                self.__tail = self.__tail.next # tail now points to the last node

            self.__size += 1 # Increase size

        # Same as addLast 
        def add(self, e):
            self.addLast(e)

        # Insert a new element at the specified index in this list
        # The index of the head element is 0 
        def insert(self, index, e):
            if index == 0:
                self.addFirst(e) # Insert first
            elif index >= self.__size:
                self.addLast(e) # Insert last
            else: # Insert in the middle
                current = self.__head
                for i in range(1, index):
                    current = current.next
                temp = current.next
                current.next = self.Node(e)
                (current.next).next = temp
                self.__size += 1

        # Return true if the list is empty
        def isEmpty(self):
            return self.__size == 0

        # Return the size of the list
        def getSize(self):
            return self.__size

        def __str__(self):
            result = ""

            current = self.__head
            for i in range(self.__size):
                result += str(current.element)
                current = current.next
                if current != None:
                    result += ", " # Separate two elements with a comma
            result = re.sub('[\(\)\{\}<>]', '', result)
            return result

        # Clear the list */
        def clear(self):
            self.__head = self.__tail = None

        # Return elements via indexer
        def __getitem__(self, index):
            return self.get(index)

        # Return an iterator for a linked list
        def __iter__(self):
            return LinkedListIterator(self.__head)
class LinkedListIterator:
    def __init__(self, head):
        self.current = head

    def __next__(self):
        if self.current == None:
            raise StopIteration
        else:
            element = self.current.element
            self.current = self.current.next
            return element

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])

输出:

full list: [3, 18, 19, 9, 2, 2, 19, 1, 10, 10]
middle value: 2