Python - リンクされたリストクラスモジュールを入力として逆転する

Question

リンクリストを入力として受け入れる問題に取り組んでいますが、現時点でリンクリストの例を設定する方法はわかりません。

私の最初の問題は、次の命令を理解されています。これは、単純に次の一環として、「逆転の要約」を定義伴うまたはPythonでリンクリストをまとめたいくつかの他の方法があるん

Write a function that accepts a linked list as input, then reverses that linked list.

を：

class Node(object): 

    # Initialize with a single datum and pointer set to None 

    def __init__(self, data=None, next_node=None): 
     self.data = data 
     self.next_node = next_node 

    # Returns the stored data 

    def get_data(self): 
     return self.data 

    # Returns the next node 

    def get_next(self): 
     return self.next_node 

    # Reset the pointer to a new node 

    def set_next(self, new_next): 
     self.next_node = new_next 

    def set_data(self, data): 
     self.data = data 

class LinkedList(object): 

    # Top node in the list created on __init__ 

    def __init__(self, head=None): 
     self.head = head 

    # Take in the new node and point the new node to the prior head O(1) 

    def insert(self, data): 
     new_node = Node(data) 
     new_node.set_next(self.head) 
     self.head = new_node 

    # Counts nodes O(n) 

    def size(self): 
     current = self.head 
     count = 0 
     while current: 
      count += 1 
      current = current.get_next() 
     return count 

    # Checks each node for requested data O(n) 

    def search(self, data): 
     current = self.head 
     found = False 
     while current and found is False: 
      if current.get_data() == data: 
       found = True 
      else: 
       current = current.get_next() 
     if current is None: 
      raise ValueError("Data not in list") 
     return current 

    # Similar to search, leapfrogs to delete, resetting previous node pointer to point to the next node in line O(n) 

    def delete(self, data): 
     current = self.head 
     previous = None 
     found = False 
     while current and found is False: 
      if current.get_data() == data: 
       found = True 
      else: 
       previous = current 
       current = current.get_next() 
     if current is None: 
      raise ValueError("Data not in list") 
     if previous is None: 
      self.head = current.get_next() 
     else: 
      previous.set_next(current.get_next()) 

Answer 1

基本的なリンクリストクラスのコードはすべてそこにあります。リンクされたリストを逆にするだけです。リンクされたリストを逆にすることは次のようになります。

[1] - > [2] - > [3] - > NULL

あなたは1頭で、3尾であることを伝えることができます（それはリンクリストにある最後のノードであるということを意味PythonではNULLまたはNoneを指しているため）。あなたがする必要があるのは、そのリンクされたリストを取得し、この結果を生成するアルゴリズムを見つけ出すことです。

[3] - > [2] - > [1] - > NULL

今3は、ヘッドであり、1がテールです。

ので、擬似コードを使用して：

Initalize 3 Nodes: prev, next, and current 
current = head 
prev = None 
next = None 
While current != None 
    next = current.next 
    current.next = prev 
    prev = current 
    current = next 
head = prev