Pythonでリンクされたノードのリストをどうやって元に戻すことができますか？

Question

コードスニペットは次のとおりです。ノードのリストを逆転しようとしましたが、そうすると、リンクされたリストの最初のノードが1つだけ印刷されます。私がここで間違って何をしているのか？私はこれを紙に書いてきました。ノードをループして、新しいリンクリストにそれぞれを追加する必要があるようです。 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には値があります。また、新しいリストは、既存のリストのノードを再利用し、オブジェクトを共有します。これは、あるリストのノードへの変更が、他のリストへの変更をもたらすので、望ましい挙動ではない可能性が高い。特に、新しい要素をそのうちの1つに追加すると、リストが奇妙に動作していることがわかります。

次のコードは、元のリストの値を逆順に含む新しいリストを作成します。

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/