Блог

 def is_palindromic_linked_list(head):

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

    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        fast = fast.next.next
        slow = slow.next

    head_second_half = reverse(slow) #6, 4, 2 => 2, 4, 6
    copy_head_second_half = head_second_half #<------HERE: copied linkedlist
    
    while (head is not None and head_second_half is not None):
        if head.value != head_second_half.value:
            break
        head = head.next
        head_second_half = head_second_half.next

    reverse(copy_head_second_half) #<---HERE: reversed the copied version of the linkedlist to set it back to how it was. 

    if head is None or head_second_half is None:
        return True

    return False

def reverse(head):
    
    prev = None

    while (head is not None):

        next = head.next
        head.next  = prev
        prev = head
        head = next

    return prev
 

как в этом есть какой-то смысл? Работает ли связанный список иначе, чем переменные, в которых изменение скопированной версии изменяет оригинал?

Проблема возникает, когда в игру вступают изменяемые объекты. В вашем случае вы ссылаетесь на один и тот же объект, а это означает, что каждая метка указывает на один и тот же объект. На эту тему слишком много можно сказать, но я предлагаю прочитать что-нибудь, начиная отсюда

Когда вы напрямую назначаете исходный список списку копирования, вы ссылаетесь на него.

Вам нужно использовать функцию copy(), в зависимости от того, есть ли в вашем списке другие объекты, вам, возможно, придется использовать функцию deepCopy (), все это объясняется в ссылке.

Использование с вашим примером:

• мелкая копия

Неглубокая копия создает новый составной объект, а затем (насколько это возможно) вставляет в него ссылки на объекты, найденные в оригинале.

 
    copy_head_second_half = head_second_half.copy() #<------HERE: copied linkedlist

 

• Глубокое копирование

Глубокая копия создает новый составной объект, а затем рекурсивно вставляет в него копии объектов, найденных в оригинале.

 
    copy_head_second_half = head_second_half.deepCopy() #<------HERE: copied linkedlist

 

Как уже отмечалось, copy_head_second_half переменная получает ссылку на головной узел перевернутого связанного списка. Никакие узлы не копируются. Но , пожалуйста, обратите внимание, что список уже мутирован reverse , поэтому, даже если бы вы думали, что копируете список с этим заданием, это произошло бы слишком поздно: мутация исходного списка уже произошла.

Вам нужна эта copy_head_second_half переменная не потому, что вам нужна копия всего списка, а потому, что вам нужно сохранить ссылку на этот головной узел, пока head_second_half он будет указывать на другие узлы в следующем цикле. Без этой скопированной ссылки вы бы потеряли, с чего начинался этот второй список!

Верно, исходный список мутирует при вызове reverse , но именно поэтому ваш код вызывает reverse снова: таким образом, мутация будет отменена, и ваш список вернется в исходное состояние, когда функция вернется.

На самом деле это хорошая практика: вы не выделяете память для создания копии половины списка.