1つのリンクリストを逆転させる再帰的な実装についての質問

Question

挿入順が5,4,3のリンクリストを作成した場合。リンク先のリストが3->4->5->nullというように格納されるように、頭参照を使用します。

リンクされたリストを元に戻したいときは、元の挿入順になるので
5->4->3->nullです。これで私の新しいリストがどのように見えているのか、私の頭参照が参照するべきノードはどのようなものなので、リストに追加する新しい要素にはまだO（1）の挿入時間がありますか？

Answer 1

頭は定義上、常にリストの最初の要素を指していると思います。

O（1）のリンクリストの最後に挿入する場合は、1つは最初の要素に、もう1つは最後の要素に2つの参照を保持します。最後に追加するには、最後の要素への最後の参照をたどり、最後の要素を超えて新しい要素を追加し、最後の参照を更新して新しい最後の要素を指すようにします。

最後の参照だけでなく、最初の参照と最後の参照の両方を設定する必要があるため、空のリストに挿入することは特別なケースになります。 1つの要素を持つリストから削除する場合も同様です。

Answer 2

単独でリンクされたリストの背後にある場合は、最後の要素への参照を保持する必要があります。新しい要素を挿入する場合は、新しい要素を頭に、新しい要素を末尾に挿入して新しいリンクオブジェクトを作成し、挿入した要素の新しい末尾に新しいリンクオブジェクトを作成しますその後。これは、3つのポインタの動き、したがって一定の時間を要する。それの

Answer 3

と思いますこのよう：

HEAD -> [the rest of the list]からなるリストの逆が正確である：reverse([the rest of the list]) -> HEAD。

リストにという単一の要素が含まれていると、基本ケースになります。そのようなリストの逆はそれだけである。これはOでないこと

class Node(object): 

    def __init__(self, data, next_=None): 
     self._data = data 
     self._next = next_ 

    def __str__(self): 
     return '[%s] -> %s' % (self._data, 
       self._next or 'nil') 


def reverse(node): 
    # base case 
    if node._next is None: 
     return node 

    # recursive 
    head = Node(node._data)  # make a [HEAD] -> nil 
    tail_reverse = reverse(node._next) 

    # traverse tail_reverse 
    current = tail_reverse 
    while current._next is not None: 
     current = current._next 
    current._next = head 

    return tail_reverse 


if __name__ == '__main__': 
    head = Node(0, 
      Node(1, 
       Node(2, 
        Node(3)))) 
    print head 
    print reverse(head) 

注（1）による最終要素の参照（頭部のみ）の欠如：

ここで（別名パイソンを実行可能な擬似コードを使用して）例です。

Answer 4

O（1）の挿入時間を持つリンクされたリストの場合は、リストの前部または他の任意の場所に完全に挿入する必要があります。単独でリンクされたリストであるということは、最後の要素までのリストにはアクセスできないため、リストの最後の要素を指すことができないことを意味します。 Shannon Severanceが頭と尾の2つのポインタを保持しているという点で、Shannon Severanceが述べているように、これを修正することができます。頭部を使用してエレメントとテールにアクセスし、任意にエレメントをリストに追加することができます。