我如何在Python中反转我的节点单链表

Question

代码片段如下:试图反转我的节点列表，但是当我这样做时，只有一个节点(链表中的第一个)打印出来。知道我哪里做错了吗?我已经写在纸上了看起来它应该循环遍历节点，把每个节点都添加到新的链表中?

# node class
class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
# singly linked list class
class SinglyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
# I'm trying to do the same thing in my reverseList() method
# as I'm doing in the addFront method
def addFront(self, value):
    # create new node
    newNode = Node(value)
    # set old head to point to new node
    if self.head == None:
        self.head = newNode
        self.tail = newNode
    else:
        # store old head
        last_head = self.head
        # set head to new node
        self.head = newNode
        # point head to old head
        self.head.next = last_head
# reverseList() method not working? 
# Only giving me first head value? Why?
def reverseList(self):
        node = self.head
        newList = SinglyLinkedList()
        newList.head = None
        while node:
            if node.next == None:
                break
            else:
                temp = newList.head
                newList.head = node
                newList.head.next = temp
                print newList.head.value
                node = node.next

Answer 1

似乎您的代码跳过了列表的最后一个元素，因为您设置了node == node.next，然后询问node.next是否有值。新列表还重用现有列表的节点，从而使它们共享对象。这可能不是期望的行为，因为对一个列表的节点的任何更改都会导致对另一个列表的更改。特别是当你向其中一个添加新元素时，你会开始感到列表的行为很奇怪。

下面的代码创建了一个新列表，其中包含原列表的值以倒序排列。

def revers(self):
    rev = SinglyLinkedList()
    node = self.head
    while node:
        newNode = Node(node.value)
        if not rev.tail:
            rev.tail = newNode
        newNode.next = rev.head
        rev.head = newNode
        node = node.next
    return rev

下面的代码反转一个列表。

def revers(self):
    prev = self.head
    next = self.head.next
    prev.next = None
    while next:
        temp = next.next
        next.next = prev
        prev = next
        next = temp
    self.head, self.tail = self.tail, self.head

关于代码的注释。将函数式行为和命令式行为混合在一起通常不是一个好主意。你的addFront函数修改列表对象，而你要求的反向函数创建一个新列表。所有函数要么创建一个新列表，要么修改当前实例。像这样混合会让你很难预测列表的行为。

Answer 2

部分问题发生在newList.head = node赋值，随后是:newList.head.next = temp。第一行使这两个引用都指向相同的东西，下一行现在将改变这两个引用(因为它们现在可以互换使用)。

我认为你需要把前一个头分配到新列表的尾部:

def reverseList(self):
    node = self.head
    newList = SinglyLinkedList()
    newList.head = None
    while node:
        if node.next == None:
            break
        else:
            temp = newList.head
            newList.head = node
            newList.tail = temp
            print newList.head.value
            node = node.next

编辑:如果您不介意创建只包含旧节点对象值的新节点(对象)(这就是我认为addFront正在做的)，您应该能够简单地替换:

newList.head = node

newList.head = Node(node.value, node.next)

Answer 3

我们可以用递归函数

反转列表

def reverse (item, tail = None):
    next = item.next
    item.next = tail
    if next is None:
        return item
    else:
        return reverse(next, item)

参考:http://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/