在python中反转链表

Question

我被要求反转 a ，它以 head 作为参数，其中 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

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 ？

原文由 Ramya 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

你可以使用 mod 函数来获取每次迭代的余数，显然这将有助于反转列表。我认为你是 Mission R and D 的学生

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

原文由 coderusher 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

接受的答案对我来说没有任何意义，因为它指的是一堆似乎不存在的东西（ 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

原文由 Blckknght 发布，翻译遵循 CC BY-SA 3.0 许可协议