反向链表python

Question

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

class LinkedList:
    def __init__(self, input=None):
        self.first = None
        self.last = None
        self.index = None
        if input is not None:
            for p in input:
                new = Node(p)
                if self.first is None:
                    self.first = new
                else:
                    self.last.next = new
                self.last= new

此代码从参数创建一个链表。

t = LinkedList([1,2,[3,4],5])

将存储为：1-2-[3,4]-5 其中 - 符号是 data.next 引用。我需要这个列表的反转，我的想法是交换元素 [0]-[n],[1]-[n-1]..

def reverse(self):
    temp = self.first
    self.first = self.last
    self.last = temp
    temp = self.first.next

它交换了第一个和最后一个元素，并从一开始就将 temp 作为下一个节点，但我不知道如何继续，如何让这段代码工作？

Answer 1

一般算法如下：

维护指向两个列表开头的指针，一个旧列表和一个新列表。最初旧列表包含所有节点，新列表为空。
重复删除旧链表的第一个节点并将其添加到新链表的最前面，直到旧链表为空，新链表包含所有节点。

生成的新列表将与旧列表相反。

Answer 2

这是一个工作的例子 Node class 和 LinkedList class 以及一个 reverse 函数，它反转了单链表.这个想法是改变每个节点的内存引用。

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


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

    def reverse(self):
        current = self.head
        previous = None
        while current:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        self.head = previous

在链表的一次传递中，我们通过跟踪 current 和 previous 节点来交换每个节点的指针。该算法不需要创建新的链表来存储反向列表，并且将在线性时间内运行。我希望这有助于提供替代链表反向实现。

Answer 3

使用递归代替迭代修改@andrew 的解决方案：

def reverse(self):
    def recursive(curr, prev):
        if not curr:  # curr is None
            return prev
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

        return recursive(curr, prev)

    self.head = recursive(curr=self.head, prev=None)

反向链表python

Reverse linked list python

python

linked-list