Найти наименьший предмет в Списке с односвязными ссылками и перейти к голове? - PullRequest
Новая
       7

Найти наименьший предмет в Списке с односвязными ссылками и перейти к голове?

0 голосов
/ 14 февраля 2019

Недавно у меня была викторина, и вот как выглядел вопрос: -

Вы можете использовать следующий класс узлов: 

class Node:
  """Lightweight, nonpublic class for storing a singly linked node."""
  __slots__ = 'element', 'next'       # streamline memory usage

  def __init__(self, element, next):  # initialize node's fields
    self.element = element            # reference to user's element
    self.next = next                  # reference to next node

Предположим, у вас есть односвязный списокуникальные целые числа.Напишите метод Python, который обходит этот список, чтобы найти наименьший элемент, удаляет узел, содержащий это значение, и вставляет наименьшее значение в новый узел в начале списка.Наконец, верните указатель головы.Для простоты вы можете предположить, что узел, содержащий наименьшее значение, еще не находится в начале списка (т. Е. Вам никогда не придется удалять головной узел и повторно добавлять его снова).

Ваш методпередается заголовок списка в качестве параметра (типа Node), как в следующей сигнатуре метода:

def moveSmallest (head): вы можете использовать только класс Node;другие методы (например, size () и т. д.) недоступны.Кроме того, у вас есть только один указатель head (передается как параметр);у вас нет доступа к хвостовому указателю.

Например, если список содержит:

5 → 2 → 1 → 3, результирующий список будет содержать:

1→ 5 → 2 → 3 Подсказка 1: на этот вопрос есть несколько частей;разбить проблему и подумать о том, как выполнять каждую часть отдельно.

Подсказка 2: Если вам нужно выйти из цикла раньше, вы можете использовать команду прерывания.

Подсказка 3: Дляпустой список или список только с одним элементом, делать нечего!

Мой ответ: 

def moveSmallest(h):
 if h==None or h.next==None:
   return h

 # find part
 temp=h
 myList=[]
 while temp!=None:
   myList.append(temp.element)
   temp=temp.next
 myList.sort()
 sv=myList[0]

 # remove part
 if h.element==sv and h.next!=None:
   h=h.next
 else:
   start=h
   while start!=None:
     if start.next.element==sv and start.next.next!=None:
       start.next=start.next.next
       break
     if start.next.element==sv and start.next.next==None:
       start.next=None
       break
     start=start.next

 # Insert part
 newNode=Node(sv)
 newNode.next=h
 h=newNode
 return h

Отметка получена = 10/30

Отзыв на мойответ:

"Не предполагается использовать сортировку; поиск в списке должен быть таким, каким мы его рассмотрели в классе.

Вы продвигаетесь слишком далеко вперед в списке, не проверяя, существуют ли узлы.

Просмотрите слайды «односвязного списка» и ответьте на этот вопрос, как подсказывают примеры.это к списку в качестве головного узла.Я запустил этот код, и он отлично работает.Как видно из отзыва, он говорит: «Вы продвигаетесь слишком далеко вперед в списке, не проверяя, существуют ли узлы».о котором позаботился первый оператор if в моем ответе и «Не предполагается использовать сортировку; поиск в списке должен быть таким, каким мы его рассмотрели в классе».Я считаю, что моей ошибкой было использование списка на первом месте, но, учитывая код, окончательный результат должен быть больше 20/30.Ребята, не могли бы вы проверить это или высказать свое мнение об этом отзыве?

1 Ответ

0 голосов
/ 14 февраля 2019

Как видно из отзыва, он говорит: «Вы продвигаетесь слишком далеко вперед в списке, не проверяя, существуют ли узлы».о котором позаботился первый оператор if в моем ответе

Это не позаботилось.Первый оператор if вашей функции просто проверяет, существует ли заголовок и существует ли узел, следующий за заголовком (в основном, утверждая, что у вас есть как минимум два узла в связанном списке).

Чтоу вас есть: 

if h.element==sv and h.next!=None:
   h=h.next
 else:
   start=h
   while start!=None:
     if start.next.element==sv and start.next.next!=None:

Если вы входите в цикл while, вы знаете только следующее:

  1. В вашем связанном списке есть как минимум два элемента
  2. h.element! = sv или h.next == Нет
  3. Текущий узел не является None

Однако узел, следующий за текущим узлом (start.next), может быть Noneв какой-то момент - когда вы достигнете конца вашего связанного списка.Поэтому вы пытаетесь получить доступ к несуществующему узлу.

Вот как я бы это сделал.Я не проверял это, но я уверен, что это работает: 

def moveSmallest(head):

    if head is None or head.next is None:
        return head

    # First, determine the smallest element.
    # To do this, we need to visit each node once (except the head).
    # Create a cursor that "iterates" through the nodes
    # (The cursor can start at the 2nd element because we're guaranteed the head will never have the smallest element.)
    cursor = head.next
    current_minimum = head.next.element
    while cursor is not None:
        if current_minimum > cursor.element:
            # We've found the new minimum.
            current_minimum = cursor.element
        cursor = cursor.next

    # At this point, current_minimum is the smallest element.
    # Next, go through the linked list again until right before we reach the node with the smallest element.
    cursor = head
    while cursor.next is not None:
        if cursor.next.element == current_minimum:
            # We want to reconnect the arrows.
            if cursor.next.next is None:
                cursor.next = None
            else:
                cursor.next = cursor.next.next
            break

    new_node = Node(current_minimum, head)
    head = new_node
    return head
...