如何从中间左右交替打印Python链表中的元素？

Question

我在 Python 中有链表这样

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SInglylInkedList:
    def __init__(self):
        self.headval = None

lst = SInglylInkedList()
lst.headval = Node("Jan")
e2 = Node("Feb")
e3 = Node("Mar")
e4 = Node("Apr")
e5 = Node("May")
e6 = Node("June")
e7 = Node("July")
e8 = Node("Aug")
e9 = Node("Sep")
e10 = Node("Oct")
e11 = Node("Nov")
e12 = Node("Dec")

lst.headval.nextval = e2

e2.nextval = e3
e3.nextval = e4
e4.nextval = e5
e5.nextval = e6
e6.nextval = e7
e7.nextval = e8
e8.nextval = e9
e9.nextval = e10
e10.nextval = e11
e11.nextval = e12

现在这个方法将按顺序打印元素

def listprint(self):
    printval = self.headval
    while printval is not None:
        print (printval.dataval)
        printval = printval.nextval

Jan → Feb → Mar → Apr → May → June → July → Aug → Sep → Oct → Nov → Dec

我想打印元素从中间左右交替打印

June → July → May → Aug → Apr → Sep → Mar → Oct → Feb → Nov → Jan → Dec

帮我写打印方法

Answer 1

由于您没有针对该问题展示自己的代码，我将只提供一些算法的想法。（您显示代码以设置链接列表并像往常一样打印它，但没有代码尝试解决实际问题。）如果我要向您显示一些代码，请先做更多的工作并将其显示在您的问题中。

一种解决方案是将链表转换为标准 Python list。然后您找到此列表的长度，然后生成所需的索引，访问与这些索引关联的值。在您的特定示例中，列表的长度为 12，因此您按以下顺序生成这些索引：

5, 6, 4, 7, 3, 8, 2, 9, 1, 10, 0, 11

我希望你能看到那里的模式。

另一种避免标准列表的方法是构建反向链表。不需要反转整个链表，只需要反转前半部分即可。在我上面生成的那些索引中，您可以看到 sub-list 5, 4, 3, 2, 1, 0，它是列表的前半部分。您可以构建该列表，然后交替使用反转的 first-half 和原始列表的后半部分进行打印。

但那样可能仍然会占用内存来复制你的一半列表。您可以通过使用堆栈或递归以相反的顺序访问列表的前半部分来避免该内存。这仍然使用内存，但只是用于指向列表项的指针。（我的意思是内存中基本级别的指针——Python 隐藏了实际的指针。）

如果您想了解更多细节，请展示更多您自己的作品，我很乐意用文字和代码进行更多解释。

Answer 2

调戏了一下，重新实现了SinglyLinkedListclass，但思路是一样的。要生成交替模式 - 当您遍历节点时 - 您可以使用堆栈来跟踪节点直到原始链表的中间。一旦你在中间，你就不再将节点压入堆栈，你只从堆栈弹出并追加到你的新链表，同时追加你正在查看的当前节点。

class Node:

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class SinglyLinkedListIterator:

    def __init__(self, node):
        self.node = node

    def __iter__(self):
        return self

    def __next__(self):
        if self.node is None:
            raise StopIteration
        node, self.node = self.node, self.node.right
        return node

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = self.head
        self.length = 0

    def __len__(self):
        return self.length

    def __iter__(self):
        return SinglyLinkedListIterator(self.head)

    def append(self, *values):
        for value in values:
            node = Node(value)
            if self.head is None:
                self.head = node
            else:
                self.tail.right = node
            self.length += 1
            self.tail = node

    def display(self):
        for node in iter(self):
            print(node.value, end=[" -> ", "\n"][node is self.tail])

    @staticmethod
    def to_alternate(linked_list):
        linked_list_alt = SinglyLinkedList()
        node_stack = []
        length = len(linked_list)
        for index, node in enumerate(linked_list):
            if index <= (length // 2) - [1, 0][length%2]:
                node_stack.append(node)
            else:
                linked_list_alt.append(node_stack.pop().value)
                linked_list_alt.append(node.value)
        while node_stack:
            linked_list_alt.append(node_stack.pop().value)
        return linked_list_alt

def main():

    linked_list = SinglyLinkedList()

    months = ["Jan", "Feb", "Mar", "Apr", "May", "June", "July", "Aug", "Sep", "Oct", "Nov", "Dec"]
    linked_list.append(*months)
    linked_list.display()

    SinglyLinkedList.to_alternate(linked_list).display()

    return 0


if __name__ == "__main__":
    import sys
    sys.exit(main())

输出：

Jan -> Feb -> Mar -> Apr -> May -> June -> July -> Aug -> Sep -> Oct -> Nov -> Dec
June -> July -> May -> Aug -> Apr -> Sep -> Mar -> Oct -> Feb -> Nov -> Jan -> Dec

Answer 3

我想你的问题是想写

lst.headval.nextval = e2 instead of lst.headval.nextval = e12，正确吗？

一个快速而肮脏的解决方案是

def listprint_answer(self):
    topval = self
    bottomval = self.nextval
    while bottomval.nextval is not None:
       newtopval=lst.headval
       while newtopval.nextval is not topval:
           newtopval=newtopval.nextval
       print(topval.dataval)
       topval=newtopval
       print(bottomval.dataval)
       bottomval=bottomval.nextval
    print(lst.headval.dataval)
    print(bottomval.dataval)
listprint_answer(e6)

如何从中间左右交替打印Python链表中的元素？

How to print elements in Python linked list alternatively left and right from middle?

python

linked-list

data-structures

singly-linked-list