[Neetcode/Linked List] Reorder Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        # 1. Find the middle of the list (slow & fast pointer)
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Reverse the second half of the list
        prev = None # Initialize prev pointer for reversal
        curr = slow.next # Start of the second half
        slow.next = None # Split the list into two halves

        # Reverse the second half in-place
        while curr:
            next_node = curr.next # Store next node
            curr.next = prev  # Reverse the link
            prev = curr # Move prev forward
            curr = next_node # Move curr forward
            
        # 3. Merge two halves: first half and reversed second half
        first = head  # Pointer to start of first half
        second = prev # Pointer to start of first half

        while second:
            tmp1 = first.next
            tmp2 = second.next

            first.next = second
            second.next = tmp1

            first = tmp1
            second = tmp2