时间戳

首页 > 解决方案 > 仅反转字符链接列表中的元音

python - 仅反转字符链接列表中的元音

问题描述

例如我有一个单链表 'a' --> 'b' --> 'q' --> 'o' --> 'r' --> 'e'

如何只反转元音，所以列表看起来像这样： 'e' --> 'b' --> 'q' --> 'o' --> 'r' --> 'a' ？

标签： pythonalgorithmlinked-list

解决方案

我将做出以下假设：

  • 反转不应该改变节点的值，而是真正移动涉及的节点对象
  • 该算法应使用恒定的额外空间。所以这不包括使用数组、堆栈、递归、另一个链表等来临时跟踪需要移动的节点。

1. 提出的算法

粗略的想法是：

  1. 在链表中查找元音的第一个和最后一个出现

  2. 如果没有找到两个不同的节点，则结束算法

  3. 交换已识别的两个节点。为了使交换成为可能，我们需要跟踪匹配节点之前的两个节点。

  4. 从步骤 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 = 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"

这些查找方法接受可选参数来指示从哪里开始和停止搜索。这样我们可以将搜索限制在链表中的子列表中。

请注意，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)

当while没有匹配项（prev1并且prev2都将是None）或只有一个匹配项（prev1并且prev2都将是单个匹配项）时，条件将不成立。后者发生在整个列表中有奇数个匹配节点时：其中的中间节点不必移动。

请注意，随着执行更多迭代，节点引用通常如何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.时间复杂度

由于对额外空间的自我限制，算法的时间复杂度不可能是O(n)。在最坏的情况下（几乎）所有节点都有元音，因此主循环的迭代次数与搜索匹配节点所需的迭代次数相结合，使该算法的时间复杂度为O(n²)。

要获得 O(n) 的时间复杂度，您需要使用O(n)空间。如果这是首选，则将所有节点放入一个数组中，使用该数组中从两端相互移动的两个索引，并交换匹配的节点。最后在一次扫描中重新连接数组中的节点，并更新链表以将数组中的第一个节点作为其头部。这是非常微不足道的......感觉就像在作弊。它真正解决了基于数组的问题，而不是基于链表的问题。所以我没有去。

推荐阅读