python - 单向链表的反向链接方向

Question

我有一个反向链接的链表，在这个程序中有什么方法可以改变链接的方向吗？我试过使用 self.head.set_next 从第一个元素开始，但是类型 None 没有方法 set_next，所以我我不确定我将如何进行。

class Node2(object):
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def set_next(self, new_next):
        self.next_node = new_next

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next_node

class LinkedList2(object):
    def __init__(self, head=None):
        self.head = head

    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node

Answer 1

这样的东西就可以了

# linked_list is the list you want to reverse
previous_node = None
current_node = linked_list.head

while current_node is not None:
    next_node = current_node.get_next()
    current_node.set_next(previous_node)
    previous_node, current_node = current_node, next_node

linked_list.head = previous_node

这将在线性时间内执行。

但是，如果你发现你需要频繁地反向链表，你可能会发现doubly linked lists更贴合您的需求