例如，我有一个单独链接的列表'a'->'b'->'q'->'o'->'r'->'e’
如何只反转元音，因此列表如下所示："e"-->"b'->'q'->'o'->'r'->'a？
我将做出以下假设：
- 反转不应更改节点的值，而是真正移动所涉及的节点对象
- 该算法应使用常量额外空间。因此，这排除了数组、堆栈、递归、其他链表的使用。。。以临时跟踪需要移动的节点
1.建议的算法
大致想法是：
-
在链接列表中查找元音的第一个和最后一个
-
如果没有找到两个不同的节点，则结束算法
-
交换已标识的两个节点。为了使交换成为可能，我们需要跟踪在匹配节点之前的两个节点。
-
从步骤1开始重复，但仅在列表的中间范围内搜索在当前迭代中识别和交换的两个节点之间的。
由于这个中间范围会越来越小，算法保证会结束。
交换功能需要处理一些特殊情况：
-
如果要交换的两个节点相邻，则需要特别小心地执行正确的"；重新布线"；
-
如果第一个节点也是列表的第一个节点(即它的头)，那么我们实际上没有它的前节点。因此，这也是一个需要处理的特殊情况。我建议将链表对象视为一个特殊的(无值的)节点，这样在这种情况下，前面的节点实际上可以是列表对象。请参见下文。
2.链表实现
核心链表实现可能如下所示：
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
class LinkedList(Node):
def __init__(self):
# LinkedList is implemented as a sentinel Node.
# Its next property represents the head
# We provide some dummy value ("HEAD"), but that should never be used
super().__init__("HEAD")
# Create a new Node for the given value and add it in front of the list
def prepend(self, val):
self.next = Node(val, self.next)
# Create new Nodes for each value in the sequence and prepend them to the list
def prependsequence(self, seq):
for val in reversed(seq):
self.prepend(val)
# Iterate the values in the list
def __iter__(self):
node = self.next
while node:
yield node.val
node = node.next
这定义了Node和LinkedList。我选择让LinkedList从Node继承，这样它也有一个next属性，在其他实现中会被称为head。但我喜欢与Node的相似之处：链表对象现在的行为就像一种哨兵节点，尽管这个术语更适用于双链表。好处是显而易见的：代码变得更简单，因为它很少需要区分"；真实的"；节点和列表对象。A"；真实的"；节点现在总是有一个前面的节点。特别是，列表的第一个节点将以列表对象作为其前身。
有了这个实现，你可以创建一个列表，在它前面添加新的节点，并迭代其中的值
a = LinkedList()
a.prependsequence("facetious") # add all these letters in one go
print(list(a)) # ['f', 'a', 'c', 'e', 't', 'i', 'o', 'u', 's']
3.算法的实现
上面的实现扩展了更多的方法：
# Find the first occurrence of a value in the given range of the list
def find(self, condition, prev=None, last=None):
if not prev:
prev = self # the list object serves as a sentinel node
while prev != last and prev.next:
if condition(prev.next.val):
return prev
prev = prev.next
# Find the first and last occurrence of a value in the given range of the list
def findfirstlast(self, condition, prev=None, last=None):
prev1 = prev2 = found = self.find(condition, prev, last)
while found:
prev2, found = found, self.find(condition, found.next, last)
# return the nodes that precede the matching two nodes
# if not found: None, None
# if only one match found: prev1 == prev2
return prev1, prev2
# Swap the nodes that follow the given two nodes
def swap(self, prev1, prev2):
if prev1 == prev2:
return
if prev2.next == prev1: # adjacent nodes given in opposite order
prev1, prev2 = prev2, prev1
node1, node2 = prev1.next, prev2.next
if node1 == prev2: # adjacent nodes
prev2.next, node2.next = node2.next, node1
else: # not adjacent nodes
prev2.next, node2.next, node1.next = node1, node1.next, node2.next
prev1.next = node2
因此，我们有基于条件查找节点的方法。该条件应该是一个回调函数，它将返回一个布尔值，指示节点是否匹配该条件。例如，查找元音的条件是：
lambda val: val in "aeiouAEIOU"
这些find方法接受可选的参数来指示从何处开始和停止搜索。通过这种方式，我们可以将搜索限制在链接列表中的子列表中。
请注意，prev参数是位于该搜索范围内的第一个节点之前的节点。函数返回在匹配节点之前的节点。这是允许调用者可能重新连接列表以删除或替换匹配节点所必需的。
swap方法执行这样的重新布线。因此，它还需要在节点之前的两个节点进行交换。请记住，前面的节点可能是链表对象本身，这意味着列表的头将被交换。
有了这些基本操作，该算法可以用一种额外的方法来实现：
# The method that performs the requested task based on a callback function
def reversewhen(self, condition):
prev1, prev2 = self.findfirstlast(condition)
while prev1 != prev2:
self.swap(prev1, prev2)
prev1, prev2 = self.findfirstlast(condition, prev1.next, prev2)
当没有匹配(prev1和prev2都将是None)或只有一个匹配(prev1和prev2都将是该单个匹配)时，while条件将不成立。后者发生在整个列表中有奇数个匹配节点时：其中中间一个不必移动。
请注意，prev1和prev2通常是随着执行更多迭代而彼此更接近的节点引用。
以下是此方法的示例执行：
a = LinkedList()
a.prependsequence("facetious")
print(list(a)) # ['f', 'a', 'c', 'e', 't', 'i', 'o', 'u', 's']
isvowel = lambda val: val in "aeiouAEIOU"
a.reversewhen(isvowel)
print(list(a)) # ['f', 'u', 'c', 'o', 't', 'i', 'e', 'a', 's']
看到它在repl.it 上运行
4.时间复杂性
由于对额外空间的自我限制，算法的时间复杂度不能小于em>O(n)。在最坏的情况下(几乎)所有节点都有元音，因此主循环的迭代次数与搜索匹配节点所需的迭代次数相结合，使该算法的时间复杂度为O(n²)。
要获得O(n)的时间复杂性，您需要使用O(n)空间。如果首选，则将所有节点放在一个数组中，使用该数组中从两端向彼此移动的两个索引，并交换匹配的节点。最后，在一次扫描中重新连接阵列中的节点，并更新链表，使阵列中的第一个节点作为其头。这很琐碎，而且。。。感觉像作弊。它真正解决了基于数组的问题，而不是基于链表的问题。所以我没有这么做。
不同语言的问题解决方案可在以下网站上获得：https://www.geeksforgeeks.org/swap-the-vowels-in-the-linked-list-representation-of-a-string/