Python：リンクされたリストがソートされているかどうかを確認する方法

Question

リンクリストの概念を理解しようとしています。私は私の質問についての情報を検索しましたが、私は私を助けてくれる回答は見つかりませんでした。 リンクリストがソートされているかどうかを確認する方法を知りたいですか？ 明らかに、私たちは普通のリストのように単純な2行の関数を使うことはできません。私は私のリストがソートされている場合（list.sort()を使用せずに）チェックしたい場合は、私はこのような機能を例えば を作成します：

def is_sorted(l): 
return all(a <= b for a, b in zip(l[:-1], l[1:])) 

しかし、リンクリストのために、私は、リストの尾と頭値を比較する必要がありますか？どのように正確に動作するのですか？

---

Contruction私はリンクリストを作成するために使用します。

class Node : 
    def __init__(self, data): 
     self.data = data 
     self.next = None 
     self.prev = None 

class LinkedList: 
    def __init__(self): 
     self.head = None   

    def add(self, data): 
     node = Node(data) 
      if self.head == None: 
       self.head = node 
      else: 
       node.next = self.head 
       node.next.prev = node      
       self.head = node    

    def search(self, k): 
     p = self.head 
     if p != None : 
      while p.next != None : 
       if (p.data == k) : 
        return p     
       p = p.next 
      if (p.data == k) : 
       return p 
     return None 

    def remove(self, p) : 
     tmp = p.prev 
     p.prev.next = p.next 
     p.prev = tmp   

    def __str__(self) : 
     s = "" 
     p = self.head 
     if p != None :  
      while p.next != None : 
       s += p.data 
       p = p.next 
      s += p.data 
     return s 

Answer 1

基本的に同じことができます。唯一の注意点は、我々はそれがソートされているかどうかをチェックすると、先ほどのリストのために書いた方法を簡単にし、ほとんど似ている、ことを持っていることを今...あなたのリンクリストを反復するための方法が必要であることを

class LinkedList: 
    ... 

    def __iter__(self): 
     p = self.head 
     while p: 
      # I yield the data for simplicity in this problem. 
      # Depending on the constraints for linked lists, it might be 
      # nicer to yield nodes. 
      yield p.data 
      p = p.next 

です：

def is_sorted(linked_list): 
    iter1 = iter(linked_list) 
    iter2 = iter(linked_list) 
    next(iter2, None) # drop the first element in iter2. 
    return all(i1 <= i2 for i1, i2 in zip(iter1, iter2)) 

リンクリストを反復処理する方法を使用すると、既に作成した他のメソッドが簡単になります。例えば

def __str__(self): 
    return ''.join(iter(self)) # Original code assumes string data, so I do too. 

Answer 2

LinkedListのが、それはPythonのリスト型と互換性になることはありません。これを呼び出します。 :-)

あなたのLinkedListクラスには、Pythonでiterableオブジェクトを作成するために必要なメソッドがありません。したがって、iterableで動作するビルトイン関数を使用することはできません。リストをチェックする新しいメソッドを書く必要があります：頭から尾まで、各要素の値が> =前のものであるかどうかを調べてください。

また、これを反復可能にするために必要なadditional methodsを探してください（という形式のメソッドが必要です）。次に、既知の解決方法を適用してください。