Как вы создаете LinkedList, который содержит циклы? - PullRequest
Новая
       48

Как вы создаете LinkedList, который содержит циклы?

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

Я пытаюсь придумать контрольный пример решения, предоставленного hackerrank для обнаружения циклов в связном списке с python.Решение, данное hackerrank: 

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

def has_cycle(head):
    fast = head;

    while(fast != None and fast.next != None):
        fast = fast.next.next;
        head = head.next;

        if(head == fast):
            return True;

    return False;

Итак, я создал следующий LinkedList 

8 -> 7 -> 6 -> 5 -> 4 -> 3
     ^                   |
     |                   V
     1 <-----------------2

Используя этот код: 

Node_1 = Node(1)
Node_2 = Node(2, Node_1)
Node_3 = Node(3, Node_2)
Node_4 = Node(4, Node_3)
Node_5 = Node(5, Node_4)
Node_6 = Node(6, Node_5)
Node_7 = Node(7, Node_6)
Node_8 = Node(8, Node_7)
Node_1 = Node(1, Node_7)

Норезультаты оказались не такими, как я ожидал: 

print(has_cycle(Node_8))  # returns False
print(Node_2.next.next)  # returns None 
print(Node_1.next.data)  # returns 7

Это сработало бы в C ++, поэтому мне кажется, что проблема в том, что я передаю копии объектов, а не их указатели.Если это так, может кто-нибудь указать мне какой-нибудь материал для изучения таких понятий, пожалуйста?

Кроме того, как бы я создал вышеупомянутый контрольный пример?

Спасибо!

1 Ответ

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

Строка: 

Node_1 = Node(1, Node_7)

создает новый узел, он не изменяет исходный Node_1, связанный с Node_2.Созданные списки выглядят так: 

8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
     ^
1 ---|

Чтобы создать цикл, вам нужен способ изменить ссылку next существующего узла.Добавьте этот метод в класс Node: 

def set_next(self, next_node = None):
    self.next = next_node

Затем замените последнюю строку на: 

Node_1.set_next(Node_7)
...