The original linked list in main changes once I try to reverse the second half of the link list but I do not understand how exactly. If anyone can give me an explanation in detail I will greatly appreciate it. I left some comments in the code explaining where I am not sure what is going on. 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() I have some comment above explaining an issue I have with my understanding of what is going on. My initial thought was to just have a variable that has the reverse second half of the link list and the rest of the code without reverting back to the original order of the link list. This does not work because when I call is_palindromic_linked_list(head) for the second time in main the link list has been modified and does not have the attribute .next To my understanding the variable slow is a pointer that points to the memory address of the start of the second half of the link list, therefore, when I reverse the second half of the linked list the my original linked list get modified as well? If this is the case, then what is happening in detail because I am having trouble understanding how reverting the reversal somehow keeps the original linked list untouched in main. What I mean by this is that in my main function if I were to print out each node from link list head without reverting back the reversal in is_palindromic_linked_list function the link list is changed and therefore at some point does not contain the .next so the second time I call this function an error occurs but by reversing back the linked list it works. I do understand that addresses are involved but I do not exactly see what is happening here because I see it as I detached the second half of the linked list so whatever I do to this link list I thought would be completely separate to the original, so what I mean is by detaching it I can see how my original link list now only contains the first half and reversing back again this detached link list (that I believe has nothing to do with my original linked list now) somehow keeps my original linked list as it was at first. I'm not sure if I make sense. I'm struggling to explain my thought process and would really like some clarification. Continue reading...
