在python中反转链表

Question

我被要求反转以head作为参数的a，其中head是一个链接列表，例如：1->；2->；3，它是从已定义的函数返回的，我试图以这种方式实现函数reverse_linked_list：

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
pass

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_reversal([1,2,3])。我编写的用于反转列表的函数是给定[3,2,1,2,1,2,1,2,1]，并且仅适用于长度为3的列表。我如何将它推广到长度为n的列表？

Answer 1

你可以使用mod函数来获取每次迭代的余数，显然这将有助于逆转列表。我想你是一个来自研发部的学生

head=None   
prev=None
for i in range(len):
    node=Node(number%10)
    if not head:
        head=node
    else:
        prev.next=node
    prev=node
    number=number/10
return head

Answer 2

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

在这个例子中，我使用previous, current, 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 -> n2 -> n3

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

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

第一次迭代

previous = None

[n1] -> [n2] -> [n3] current tmp current.next = previous

第二次迭代

[n1] -> [n2] -> [n3] previous current tmp current.next = previous

第三次迭代

# next is None

[n1] -> [n2] -> [n3] previous current current.next = previous

由于while循环在current == None时退出，列表的新头必须设置为previous，这是我们访问的最后一个节点。

已编辑

在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