Добавить узел в порядке возрастания - PullRequest
Новая
       10

Добавить узел в порядке возрастания

0 голосов
/ 12 октября 2018 
def add(self, value):
    #write your code here

    if self.head == None:
        new_node = Node(value)
        self.head = new_node
        self.tail = self.head


    elif self.head.value > new_node.value:
        new_node = Node(value)
        new_node.value = value
        new_node.next = self.head
        self.head = new_node

    else:
        new_node = Node(value)
        self.tail.setNext(new_node)
        self.tail = new_node

    self.count += 1

Выше приведен код моей функции add.Я пытаюсь добавить Node объекты в связанный список в порядке возрастания, чтобы при печати он выглядел как: 

>>> x.add(8)
>>> x.add(7)
>>> x.add(3)
>>> x.add(-6)
>>> x.add(58)
>>> x.add(33)
>>> x.add(1)
>>> x.add(-88)
>>> print(x)
Head:Node(-88) Tail:Node(58)
List:-88 -6 1 3 7 8 33 58

Но когда я делаю это с моим кодом выше, он печатает его как: 

>>> print(x)
Head:Node(-88)
Tail:Node(1)
List:-88 -6 3 7 8 58 33 1

Я на 80% уверен, что проблема в утверждении elif, но я не уверен, как это исправить, чтобы сделать это в порядке возрастания.

1 Ответ

0 голосов
/ 12 октября 2018

Проблема в последнем другом.Итак, давайте посмотрим, что происходит: число, действие, результат:

  • 8 -> в первом, если -> 8
  • 7 -> в elif 8> 7 -> 7, 8
  • 3, -6 -> то же самое в elif -> -6, 3, 7, 8

  • 58 -> последнее -> -6, 3, 7,8, 58

    и здесь появляется ошибка, когда 33 приходит и снова входит в последний, так как он больше, чем голова, равная -6, и результат становится -6, 3, 7, 8, 58, 33.

Чтобы исправить это, вам нужно пройтись по списку, чтобы увидеть, куда нужно поместить 33, вы не можете получить отсортированный список, просто разместив элементы в начале или вконец. 

def add(self, value):
    #write your code here

    #if list is empty
    if self.head == None:
        new_node = Node(value)
        self.head = new_node
        self.tail = self.head

    #elif value < head set new head
    elif self.head.value > value:
        new_node = Node(value)
        new_node.value = value
        new_node.next = self.head
        self.head = new_node


    #elif value > tail set new tail
    elif value > self.tail.value:
      new_node = Node(value)
      self.tail.setNext(new_node)
      self.tail = new_node
    # and finally you need to loop to find the sweet spot
    else:
      # we will start the search from the head
      current_node = self.head
      # while the value we wish to insert is bigger than the next one
      while value > current_node.next.value:
        # set the current one to the next one
        current_node = current_node.next
      # finally we reached a node which is smaller than the value we wish to insert
      # but its next node is bigger
      new_node = Node(value)
      # set the new nodes next to the bigger node
      new_node.next = current_node.next
      # and the curren't node's next to the new one
      current_node.next = new_node
...