再帰的にリンクされたリストを

Question

私は、リンクリストをPythonで再帰的に逆転させるアルゴリズムに問題があります。

def reverse(lis, prev = None): 
    if lis.next != None: 
     reverse(lis.next, lis) 
    lis.next = prev 

入力：3 1 4

出力：3

そのが働いていない理由を任意のアイデア？

Answer 1

問題は、あなたのリンクリストの根が同様に変更されたことである：リストを変更した後、あなたの要素3が実際に最後の要素で、あなたの関数より良いリターンルートだけでなく：

def reverse(lis, prev = None): 
    if lis.next != None: 
     temp = lis.next 
     lis.next = prev 
     return reverse(temp, lis) 
    else: 
     return lis # the new root 

は、今あなたがそれを呼び出す：

oldroot = ... #construct linked list 
newroot = reverse(oldroot) 
print(newroot) 

だからあなたの関数は正しいですが、操作の後、あなたの手の中に誤ったリンクリストの要素を持っています。

Answer 2

これは、いくつかの機能プログラミング演習のように見えるので、私はあなたに機能液（そのコピーリスト）を提示：代わりに新しいチェーンを作成する代わりに

def reverse(link, rest=None): 
    if link is None: 
     return rest 
    return reverse(link.next, LinkedList(link.value, rest)) 

class LinkedList: 
    def __init__(self, value=None, next=None): 
     self.next = next 
     self.value = value 
    def print(self): 
     print(self.value) 
     if self.next is not None: 
      self.next.print() 

def to_linked_list(items): 
    if len(items) == 0: 
     return None 
    return LinkedList(items[0], to_linked_list(items[1:])) 

to_linked_list([1, 2, 3, 4, 5]).print() 
# 1, 2, 3, 4, 5 
reverse(to_linked_list([1, 2, 3, 4, 5])).print() 
# 5, 4, 3, 2, 1 

Answer 3

：

def reverse_linked_list(node, prev=None): 
    if node.next is None: 
     node.next = prev 
     return node 
    root_node = reverse_linked_list(node.next, node) 
    node.next = prev 
    return root_node