Мобильная версияКод: Выделить всё
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def is_palindromic_linked_list(head):
if head is None or head.next is None:
return True
# find middle of the LinkedList
slow, fast = head, head
while (fast is not None and fast.next is not None):
slow = slow.next
fast = fast.next.next
'''
Here I reverse the second half of the link list.
The variable slow points to the second half of the link list and
the reversed linked list is now head_second_half.
If I print out each node, in link list head, every node prints out from the
original link list on this line before the reversal.
'''
head_second_half = reverse(slow) # reverse the second half
# store the head of reversed part to revert back later
'''
Here although I am passing slow into the reverse function to reverse the second
half of the link list my link list head gets modified and I can see this because
by printing out all nodes from link list head on this line after the reversal I
seem to only get the first half of the link list
'''
copy_head_second_half = head_second_half
# compare the first and the second half
while (head is not None and head_second_half is not None):
if head.value != head_second_half.value:
break # not a palindrome
head = head.next
head_second_half = head_second_half.next
reverse(copy_head_second_half) # revert the reverse of the second half
if head is None or head_second_half is None: # if both halves match
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
def main():
head = Node(2)
head.next = Node(4)
head.next.next = Node(6)
head.next.next.next = Node(4)
head.next.next.next.next = Node(2)
print("Is palindrome: " + str(is_palindromic_linked_list(head)))
head.next.next.next.next.next = Node(2)
print("Is palindrome: " + str(is_palindromic_linked_list(head)))
main()
< /code>
У меня есть несколько комментариев выше, объясняющая проблему, которая у меня есть с моим пониманием того, что происходит. Моя первоначальная мысль заключалась в том, чтобы просто иметь переменную, которая имеет обратную вторую половину списка ссылок и остальную часть кода, не возвращаясь к исходному порядку списка ссылок. Это не работает, потому что, когда я называю is_palindromic_linked_list (head) Насколько я понимаю, переменная медленная - это указатель, который указывает на адрес памяти начала второй половины списка ссылок, поэтому, когда я обращаю во вторую половину связанного списка мой оригинальный список связанного списка Get Модифицировано? Если это так, то то, что происходит в деталях, потому что у меня возникают проблемы с пониманием того, как возвращение отмены каким -то образом держит оригинальный связанный список нетронутым в основном. Под этим я имею в виду, что в моей основной функции , если я должен был распечатать каждый узел из головки списка ссылок, не возвращаясь обратно изменение в is_palindromic_linked_list Функция Список ссылок изменяется, и, следовательно, в какой -то момент Не содержать .next , поэтому во второй раз, когда я называю эту функцию, возникает ошибка, но возвращая обратно связанный список, который он работает. Не вижу, что здесь происходит, потому что я вижу это, когда я отделял вторую половину связанного списка, поэтому все, что я делаю с этим списком ссылок Посмотрите, как мой оригинальный список ссылок теперь содержит только первую половину и снова возвращается в этот отдельный список ссылок (который, я считаю >
Я не уверен, что имею смысл. Я изо всех сил пытаюсь объяснить свой мыслительный процесс и действительно хотел бы разъяснения.
Подробнее здесь: https://stackoverflow.com/questions/684 ... st-changed
