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.
when I reverse the second half of the linked list the my original linked list get modified as well?
Yes, as the collection of nodes is the same: no new nodes are created, only modified (their next attribute). So when in the second half of the list you modify nodes, then of course this affects the list.
It can help to visualise the list. Let's take for example a list that has values 1, 2, 3, 4, 5 and 6:
head slow
↓ ↓
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│value: 1 │ │value: 2 │ │value: 3 │ │value: 4 │ │value: 5 │ │value: 6 │
│next: —————→│next: —————→│next: —————→│next: —————→│next: —————→│next:None│
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
After executing head_second_half = reverse(slow), we have this situation:
head slow head_second_half
↓ ↓ ↓
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│value: 1 │ │value: 2 │ │value: 3 │ │value: 4 │ │value: 5 │ │value: 6 │
│next: —————→│next: —————→│next: —————→│next:None│←—————:next │←—————:next |
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
So if now you were to iterate the list that starts at head, you would get 1,2,3,4. You cannot reach nodes 5 and 6 anymore when starting at head, because the node at 4 has been made a tail node, i.e. it has no next. Obviously it cannot at the same time be a tail for the second half, and also a node that still connects to the node with value 5. It can only be in one state. And so that is how it truncates the original list.
By reversing a second time, you restore the list to its original state.
Recall that during this process there are just those 6 nodes. No other nodes are created, or copied. Only those 6 exist. The only thing that happens is that several variables are used to reference certain nodes, and that some nodes get a different next value, but we keep working with the given 6 nodes. There is no copy.