143: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTo reorder the linked list we can follow the below steps:\n\n1. Find the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTo reorder the linked list we can follow the below steps:\n\n1. Find the middle node of the linked list using slow and fast pointer approach.\n2. Reverse the second half of the linked list.\n3. Merge the first half and the reversed second half of the linked list alternatively.\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nBeats\n94.68% O(1)\n\n# Code\n```\nclass Solution:\n    def reorderList(self, head: ListNode) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n        if not head or not head.next:\n            return\n        \n        # Step 1: Find the middle of the linked list\n        slow, fast = head, head.next\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n        \n        # Step 2: Reverse the second half of the linked list\n        curr, prev = slow.next, None\n        slow.next = None # set the next of the slow to None to break the link\n        while curr:\n            nxt = curr.next\n            curr.next = prev\n            prev = curr\n            curr = nxt\n        second_half = prev\n        \n        # Step 3: Merge the first half and the reversed second half of the linked list\n        first_half = head\n        while first_half and second_half:\n            temp1, temp2 = first_half.next, second_half.next\n            first_half.next = second_half\n            second_half.next = temp1\n            first_half, second_half = temp1, temp2\n\n```
['Linked List', 'Two Pointers', 'Stack', 'Python', 'Python3']