🔧 Efficient Linked List Reordering with Python: 99% Runtime Optimization
Intuition\n Describe your first thoughts on how to solve this problem. \nTo reorder a singly linked list such that it alternates between the start and end nodes
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo reorder a singly linked list such that it alternates between the start and end nodes, you need to:\n\nFind the middle of the list.\nReverse the second half of the list.\nMerge the two halves by alternating nodes from each half.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFind the Middle: Use the slow and fast pointer technique to find the middle node of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.\n\nReverse the Second Half: Starting from the node right after the middle node, reverse the second half of the list. This involves changing the next pointers of the nodes to point in the reverse direction.\n\nMerge the Two Halves: Alternate between nodes from the first half and nodes from the reversed second half. This is done by linking nodes from the two halves together in the correct order.\n# Complexity\nTime Complexity:\n\nFinding the middle node takes \nO(n) time, where \n\uD835\uDC5B\nn is the number of nodes in the list.\nReversing the second half also takes \nO(n/2) time, which simplifies to \nO(n).\nMerging the two halves takes \nO(n) time.\nOverall, the time complexity is \nO(n).\nSpace Complexity:\n\nThe algorithm only uses a constant amount of extra space, aside from the input list. Hence, the space complexity is \nO(1).\n\n# Code\n```\n# Definition for singly-linked list.\n# class ListNode(object):\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution(object):\n    def reorderList(self, head):\n        """\n        :type head: ListNode\n        :rtype: None Do not return anything, modify head in-place instead.\n        """\n        temp = head\n\n        def findMiddle(temp):\n            slow, fast = temp, temp\n            while fast and fast.next:\n                slow = slow.next\n                fast = fast.next.next\n\n            return slow\n        \n        def reverseList(node):\n            prev, curr = None, node\n            while curr:\n                nextTemp = curr.next\n                curr.next = prev\n                prev = curr\n                curr = nextTemp\n            return prev\n        \n        def mergeList(startP, midP):\n            while midP:\n                # store the next node\n                startNext = startP.next\n                midNext = midP.next\n\n                # link node to second\n                startP.next = midP\n\n                # link mid to next node\n                midP.next = startNext\n\n                # mvoe pointer to the next one\n                startP = startNext\n                midP = midNext\n\n        middle = findMiddle(temp)\n        second_half = reverseList(middle.next)\n        middle.next = None  # Split the list into two halves\n        \n        # Merge the two halves\n        mergeList(head, second_half)       \n```\n![packied_spongebob.jpg](https://assets.leetcode.com/users/images/47aa5f7b-89de-4ac9-8fc6-f62ede7c0b12_1721754772.4776068.jpeg)\n
['Linked List', 'Two Pointers', 'Python', 'Python3']