python：如何檢查鏈表是否排序

我想了解鏈接列表的概念。我搜索了關於我的問題的信息，但我還沒有找到任何可以幫助我的答案。我想知道如何檢查鏈表是否被排序？顯然，我們不能像常規列表那樣使用簡單的兩行函數。例如，如果我想檢查我的列表進行排序（不使用list.sort()），我會創建這樣的功能：python：如何檢查鏈表是否排序

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

但對於鏈表，我應該比較列表尾部和頭部值？它是如何工作的？

我金相結構用來創建鏈表：

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

來源

2016-11-09 John Meftali

你可以做基本相同的事情。唯一需要注意的是，你需要一種方法來遍歷你的鏈接列表...

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.

來源

2016-11-09 01:10:17 mgilson

調用這個LinkedList的不會導致它成爲Python的列表類型兼容。 :-)

您的LinkedList類沒有使其成爲Python中的可迭代對象所必需的方法。因此，您不能使用可用於迭代的內置函數。你必須編寫一個新的方法來檢查列表：從頭到尾遍歷，檢查每個元素的值是否大於前一個值。

或者，查找使其成爲可迭代所需的additional methods（您需要更多方法，形式爲），然後應用已知的解決方案。

來源

2016-11-09 01:08:56 Prune

python：如何檢查鏈表是否排序

回答

相關問題