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

Question

代码片段如下：试图颠倒我的节点列表，但是当我这样做时，只有一个节点（链接列表中的第一个）打印。任何想法我在这里做错了吗？我已经写在纸上，它似乎应该循环通过我的节点，将每个添加到我的新链接列表？ newList.head.next = temp：问题的

# 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分配，随后发生。第一行使这两个引用指向相同的东西，下一行现在将改变它们（因为它们现在可以互换使用）。

我认为你需要以前的头分配给您的新名单的尾巴，当您去：

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/