educative.io

Why does head.next get overwritten?

Courses
,
#1

Why does this code , reversing the linked list, override head’s.next but the fast and slow pointers algorithm doesn’t?
the 2nd while loop only has the head and head.next is None

`front, back = head, None

while front:
temp = front.next
front.next = back
back = front
front = temp

walker = head

while walker:
print(“Next”)
walker = walker.next`

Here heads.next is retained and goes further even though fast is also pointing to head and eventually makes fast.next = None.

slow, fast = head, head

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

slow is now pointing to the middle node

head_second_half = reverse(slow) # reverse the second half
head_first_half = head

Thank you!

#2

Hi @Alex1!

The reason why head.next gets overwritten in the first example is because in the very first iteration of the loop, front = head and back = None, therefore the line front.next = back will set head.next = None.

In the second example, fast starts from the head and moves forward until it reaches the tail of the list.

#3

Ah I see, that makes sense. Thank you so much!

#4

The boiler plate for Fast,Slow pointers pattern has while loop like this,

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

Why we ‘AND’ fast and fast’s next pointer existence ? Why not just check only fast’s existence (in case loop is acyclic, at that pt fast will be Null). Correct ?