时间戳

首页 > 解决方案 > 在链表中选择偶数并制作它们的子部分

python - 在链表中选择偶数并制作它们的子部分

问题描述

我们的任务是执行以下代码。

给你一个包含 N 个整数的链表。您将对列表执行以下反向操作：

选择列表中仅包含偶数的所有子部分。例如，如果列表为 {1,2,8,9,12,16}，则选定的子部分将为 {2,8}、{12,16}。

反转选定的子部分，例如 {8,2} 和 {16,12}。

该列表现在应该是 {1,8,2,9,16,12}。

问题是它没有创建子列表并给我输出[2, 8, 12, 16]，但我想要它{2,8}, {12,16}。

下面是我的代码：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append_value(self, x):
        if not isinstance(x, Node):
            x = Node(x)
        if self.head is None:
            self.head = x
        else:
            self.tail.next = x
        self.tail = x

    def reverse_list_recursive(self, current, previous):
        if self.head is None:
            return
        elif current.next is None:
            self.tail = self.head
            current.next = previous
            self.head = current
        else:
            next = current.next
            current.next = previous
            self.reverse_list_recursive(next, current)

    def is_empty(self):
        return self.head is None

    def __str__(self):
        to_print = ''
        current = self.head
        while current:
            to_print += f'{current.data}->'
            current = current.next
        if to_print:
            return f'[{to_print[:-2]}]'
        return '[]'

这是我的功能：

    def reverse_sub_parts(self):
        sublist_list = list()
        current = self.head
        while current:
            if current.data % 2 == 0:
                sublist_list.append(current.data)
            current = current.next
        print(sublist_list)


my_list = LinkedList()
my_list.append_value(1)
my_list.append_value(2)
my_list.append_value(8)
my_list.append_value(9)
my_list.append_value(12)
my_list.append_value(16)

my_list.reverse_sub_parts()

标签： pythondata-structureslinked-list

解决方案

该循环将所有具有偶数的节点显式添加到单个列表 ( sublist_list) 中。该语句sublist_list = list()只执行一次，因此您不可能希望获得多个这样的列表。

其次，即使您设法创建了可变数量的列表，您仍然需要有逻辑来反转这些新列表（微不足道），并用反向列表替换原始列表中的原始子列表（不那么微不足道） .

最后，它并没有像这样让事情变得更容易。

我建议首先使您的reverse_list_recursive函数更加通用，因此它也可以通过让它接受另外两个参数来完成列表的一个子部分的工作：节点在该部分之前，节点在它之后。两者都是None默认的，这意味着整个列表应该被颠倒。

我还建议不要使用递归解决方案，因为这将使用与列表中的节点数成线性关系的堆栈空间，因此如果列表有数千个节点，您将遇到堆栈大小限制。

所以这是一个迭代反向函数，它接受这些额外的可选参数：

    def reverse(self, before_first=None, after_last=None):
        prev = after_last
        current = before_first.next if before_first else self.head
        while current and current != after_last:
            prev, current.next, current = current, prev, current.next
        if before_first:
            before_first.next = prev
        else:
            self.head = prev

现在真正完成了最困难的部分，因为您现在只需要识别绑定偶数节点序列的节点：

    def reverse_sub_parts(self):
        prev = None
        current = self.head
        while current:
            if current.data % 2 == 0:
                if not prev or prev.data % 2 == 1:
                    before_start = prev
            elif prev and prev.data % 2 == 0:
                self.reverse(before_start, current)
            prev = current
            current = current.next

        if prev and prev.data % 2 == 0:
            self.reverse(before_start)

推荐阅读