python : 연결된 목록이 정렬되어 있는지 확인하는 방법

나는 링크 된 목록의 개념을 이해하려고합니다. 내 질문에 대한 정보를 찾았지만 나에게 도움이 될 답변을 찾지 못했습니다. 연결된 목록이 정렬되어 있는지 확인하는 방법을 알고 싶습니다. 분명히 우리는 일반 목록처럼 단순한 두 줄 기능을 사용할 수 없습니다. 내 목록 (list.sort()를 사용하지 않고) 정렬되어 있는지 확인하려면 예를 들어, 나는이 같은 함수를 만들 수 있습니다 : python : 연결된 목록이 정렬되어 있는지 확인하는 방법

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

그러나 링크 된 목록

, 나는 목록 꼬리와 머리 값을 비교해야합니까? 그것은 정확히 어떻게 작동합니까? 내가 링크 된 목록을 만드는 데 사용할

제휴 : 이것은 LinkedList의는 파이썬의 목록 유형과 호환이 될 발생하지 않습니다 호출

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에서 iterable 객체로 만드는 데 필요한 메소드가 없습니다. 따라서 iterables에서 작동하는 내장 함수를 사용할 수 없습니다. 목록을 확인하는 새로운 방법을 작성해야합니다. 머리부터 꼬리까지 이동하고 각 요소의 값이> = 이전인지 확인해야합니다.

또는 등의 더 많은 메서드가 필요한 반복 가능하도록 만들고이 알려진 솔루션을 적용하는 데 필요한 additional methods을 찾아보십시오.

출처

2016-11-09 01:08:56 Prune

python : 연결된 목록이 정렬되어 있는지 확인하는 방법

답변

관련 문제