很抱歉问这样的问题(编程新手(：
我想使用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
但它让我无
和我的其余链表代码是：
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
要在一次传递中找到中间数字，您需要保留一个长度计数器并存储您看到的元素的完整列表。然后，可以通过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