在python中反转链表

Question

我被要求反转一个以head为参数的参数，其中as head是一个链表，例如：1-

def reverse_linked_list(head):
    temp = head
    head = None
    temp1 = temp.next
    temp2 = temp1.next
    temp1.next = None
    temp2.next = temp1
    temp1.next = temp
    return temp2

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

    def to_linked_list(plist):
    head = None
    prev = None
    for element in plist:
        node = Node(element)
        if not head:
            head = node
        else:
            prev.next = node
        prev = node
    return head

    def from_linked_list(head):
    result = []
    counter = 0
    while head and counter < 100: # tests don't use more than 100 nodes, so bail if you loop 100 times.
        result.append(head.value)
        head = head.next
        counter += 1
    return result

    def check_reversal(input):
        head = to_linked_list(input)
        result = reverse_linked_list(head)
        assert list(reversed(input)) == from_linked_list(result)

它是这样调用的：check\u reversion（[1,2,3]）。我编写的用于反转列表的函数给出了[3,2,1,2,1,2,2,1]，并且只适用于长度为3的列表。如何将其概括为长度n的列表？

Answer 1

下面是一种“就地”反转列表的方法。它以恒定时间O（n）运行，并且使用零额外空间。

def reverse(head):
  if not head:
    return head
  h = head
  q = None
  p = h.next
  while (p):
    h.next = q
    q = h
    h = p
    p = h.next
  h.next = q
  return h

这里有一个动画来显示算法正在运行。
（#为动画目的象征空/无）

Answer 2

我发现blckknght的答案很有用，而且肯定是正确的，但我很难理解到底发生了什么，这主要是因为Python的语法允许在一行上交换两个变量。我还发现变量名有点混乱。

在这个例子中，我使用以前的，当前的，tmp。

def reverse(head):
    current = head
    previous = None

    while current:
        tmp = current.next
        current.next = previous   # None, first time round.
        previous = current        # Used in the next iteration.
        current = tmp             # Move to next node.

    head = previous

以具有3个节点的单链表（head=n1，tail=n3）为例。

n1-

在第一次进入while循环之前，previous被初始化为None，因为头部之前没有节点（n1）。

我发现想象变量previous、current、tmp沿着链接列表“移动”是很有用的，总是按照这个顺序。

第一次迭代

previous=None

[n1]-

第二次迭代

[n1]-

第三次迭代

# next is None

[n1]-

因为而循环退出时当前==无列表的新头部必须设置为前一个，这是我们访问的最后一个节点。

编辑

在Python中添加完整的工作示例（带有注释和有用的str表示）。我使用的是tmp而不是next，因为next是一个关键字。然而，我碰巧认为这是一个更好的名字，使算法更清晰。

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

    def __str__(self):
        return str(self.value)

    def set_next(self, value):
        self.next = Node(value)
        return self.next


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

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current))
            current = current.next

        return ' -> '.join(values)

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

        while current.next:
            # Remember `next`, we'll need it later.
            tmp = current.next
            # Reverse the direction of two items.
            current.next = previous
            # Move along the list.
            previous = current
            current = tmp

        # The loop exited ahead of the last item because it has no
        # `next` node. Fix that here.
        current.next = previous

        # Don't forget to update the `LinkedList`.
        self.head = current


if __name__ == "__main__":

    head = Node('a')
    head.set_next('b').set_next('c').set_next('d').set_next('e')

    ll = LinkedList(head)
    print(ll)
    ll.revevse()
    print(ll)

后果

a -> b -> c -> d -> e
e -> d -> c -> b -> a

Answer 3

被接受的答案对我来说毫无意义，因为它指的是一堆似乎不存在的东西（number，node，len作为一个数字而不是一个函数）。因为这个作业可能已经很久了，我将发布我认为最有效的代码。

这用于执行破坏性反转，其中修改现有列表节点：

def reverse_list(head):
    new_head = None
    while head:
        head.next, head, new_head = new_head, head.next, head # look Ma, no temp vars!
    return new_head

函数的一个不太奇特的实现将使用一个临时变量和几个赋值语句，这可能更容易理解：

def reverse_list(head):
    new_head = None  # this is where we build the reversed list (reusing the existing nodes)
    while head:
        temp = head  # temp is a reference to a node we're moving from one list to the other
        head = temp.next  # the first two assignments pop the node off the front of the list
        temp.next = new_head  # the next two make it the new head of the reversed list
        new_head = temp
    return new_head

另一种设计是在不改变旧列表的情况下创建一个全新的列表。如果要将列表节点视为不可变对象，则更合适：

class Node(object):
    def __init__(self, value, next=None): # if we're considering Nodes to be immutable
        self.value = value                # we need to set all their attributes up
        self.next = next                  # front, since we can't change them later

def reverse_list_nondestructive(head):
    new_head = None
    while head:
        new_head = Node(head.value, new_head)
        head = head.next
    return new_head