3 steps to solve the question
Reordering a linked list can be a challenging problem, but with the right approach, it becomes manageable. In this article, we’ll explain the theory behind solv
Reordering a linked list can be a challenging problem, but with the right approach, it becomes manageable. In this article, we\u2019ll explain the theory behind solving this problem and provide a step-by-step explanation of the solution. We\u2019ll also visualize the key steps for better understanding.\n\n# Solution Video\n\nhttps://youtu.be/I4DPcLkgUmA\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 11,972\nThank you for your support!\n\n---\n\n## Problem Statement\n\nGiven the head of a singly linked list, reorder the list in the following manner:\n\n- The first element is followed by the last element.\n- The second element is followed by the second-to-last element.\n- And so on.\n\nFor example:\n\n- Input: `1 \u2192 2 \u2192 3 \u2192 4 \u2192 5`\n- Output: `1 \u2192 5 \u2192 2 \u2192 4 \u2192 3`\n\n### Constraints\n\n1. You must solve the problem in-place (i.e., without using extra memory for another list).\n2. The algorithm should run efficiently.\n\n---\n\n## Approach and Theory\n\nThe solution can be broken down into three key steps:\n\n### Step 1: Splitting the List into Two Halves\n\nUsing the **two-pointer technique**, we can identify the middle of the list:\n\n- `slow` moves one step at a time.\n- `fast` moves two steps at a time.\n\nWhen `fast` reaches the end, `slow` will be at the midpoint of the list.\n\nExample:\n\n- Input: `1 \u2192 2 \u2192 3 \u2192 4 \u2192 5`\n- After splitting: `1 \u2192 2 \u2192 3` and `4 \u2192 5`\n\n### Step 2: Reversing the Second Half\n\nNext, we reverse the second half of the list. Starting from the node after `slow`, we use a standard iterative reversal process to reverse the pointers.\n\nExample:\n\n- Before reversing: `4 \u2192 5`\n- After reversing: `5 \u2192 4`\n\n### Step 3: Merging the Two Halves\n\nFinally, we merge the two halves alternately:\n\n- Take a node from the first half, then a node from the reversed second half.\n- Repeat until all nodes are merged.\n\nExample:\n\n- First half: `1 \u2192 2 \u2192 3`\n- Reversed second half: `5 \u2192 4`\n- Merged: `1 \u2192 5 \u2192 2 \u2192 4 \u2192 3`\n\n---\n\n## Visual Explanation\n\n### Initial List\n```\n1 \u2192 2 \u2192 3 \u2192 4 \u2192 5\n```\n\n### Step 1: Splitting the List\n\n1. Initialize `slow` and `fast` to the head of the list.\n2. Move `slow` one step and `fast` two steps at a time.\n\n```\nslow: 3\nfast: null (end of the list)\n```\n\nList is split:\n```\nFirst half: 1 \u2192 2 \u2192 3\nSecond half: 4 \u2192 5\n```\n\n---\n\n### Step 2: Reversing the Second Half\n\nUsing an iterative reversal process:\n\n- Start with `node = null` and `second = 4 \u2192 5`.\n\n1. Reverse 4:\n```\nnode: 4 \u2192 null\nsecond: 5\n```\n\n2. Reverse 5:\n```\nnode: 5 \u2192 4 \u2192 null\nsecond: null\n```\n\nReversed second half:\n```\n5 \u2192 4\n```\n\n---\n\n### Step 3: Merging the Two Halves\n\n1. Initialize:\n   - `first = 1 \u2192 2 \u2192 3`\n   - `second = 5 \u2192 4`\n\n2. Merge nodes alternately:\n\n   - Take `1` from `first` and `5` from `second`:\n     ```\n     1 \u2192 5\n     ```\n\n   - Take `2` from `first` and `4` from `second`:\n     ```\n     1 \u2192 5 \u2192 2 \u2192 4\n     ```\n\n   - Take `3` from `first` (second is now null):\n     ```\n     1 \u2192 5 \u2192 2 \u2192 4 \u2192 3\n     ```\n\n---\n\nhttps://youtu.be/pCc4kR-TdYs\n\n---\n\n\n## Complete Code\n\n```python []\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        fast = head\n        slow = head\n\n        # Step 1: Find the middle of the list\n        while fast and fast.next:\n            fast = fast.next.next\n            slow = slow.next\n\n        # Step 2: Reverse the second half of the list\n        second = slow.next\n        slow.next = None\n        node = None\n\n        while second:\n            temp = second.next\n            second.next = node\n            node = second\n            second = temp\n\n        # Step 3: Merge the two halves\n        first = head\n        second = node\n\n        while second:\n            temp1, temp2 = first.next, second.next\n            first.next, second.next = second, temp1\n            first, second = temp1, temp2\n```\n```javascript []\nvar reorderList = function(head) {\n    if (!head) return;\n\n    // Step 1: Find the middle of the list\n    let slow = head, fast = head;\n    while (fast && fast.next) {\n        slow = slow.next;\n        fast = fast.next.next;\n    }\n\n    // Step 2: Reverse the second half of the list\n    let second = slow.next;\n    slow.next = null;\n    let node = null;\n\n    while (second) {\n        const temp = second.next;\n        second.next = node;\n        node = second;\n        second = temp;\n    }\n\n    // Step 3: Merge the two halves\n    let first = head;\n    second = node;\n\n    while (second) {\n        const temp1 = first.next, temp2 = second.next;\n        first.next = second;\n        second.next = temp1;\n        first = temp1;\n        second = temp2;\n    }    \n};\n```\n```java []\nclass Solution {\n    public void reorderList(ListNode head) {\n        if (head == null) return;\n\n        // Step 1: Find the middle of the list\n        ListNode slow = head, fast = head;\n        while (fast != null && fast.next != null) {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n\n        // Step 2: Reverse the second half of the list\n        ListNode second = slow.next;\n        slow.next = null;\n        ListNode node = null;\n\n        while (second != null) {\n            ListNode temp = second.next;\n            second.next = node;\n            node = second;\n            second = temp;\n        }\n\n        // Step 3: Merge the two halves\n        ListNode first = head;\n        second = node;\n\n        while (second != null) {\n            ListNode temp1 = first.next, temp2 = second.next;\n            first.next = second;\n            second.next = temp1;\n            first = temp1;\n            second = temp2;\n        }        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        if (!head) return;\n\n        // Step 1: Find the middle of the list\n        ListNode* slow = head;\n        ListNode* fast = head;\n        while (fast && fast->next) {\n            slow = slow->next;\n            fast = fast->next->next;\n        }\n\n        // Step 2: Reverse the second half of the list\n        ListNode* second = slow->next;\n        slow->next = nullptr;\n        ListNode* node = nullptr;\n\n        while (second) {\n            ListNode* temp = second->next;\n            second->next = node;\n            node = second;\n            second = temp;\n        }\n\n        // Step 3: Merge the two halves\n        ListNode* first = head;\n        second = node;\n\n        while (second) {\n            ListNode* temp1 = first->next;\n            ListNode* temp2 = second->next;\n            first->next = second;\n            second->next = temp1;\n            first = temp1;\n            second = temp2;\n        }\n    }\n};\n```\n\n---\n\n## Complexity Analysis\n\n1. **Time Complexity**: $$O(n)$$\n   - Finding the middle takes $$O(n)$$.\n   - Reversing the second half takes $$O(n/2)$$.\n   - Merging the two halves takes $$O(n)$$.\n\n2. **Space Complexity**: $$O(1)$$\n   - The algorithm uses constant extra space as it modifies the list in-place.\n\n---\n\n## Conclusion\n\nBy splitting the list, reversing the second half, and merging the halves, we can reorder the list efficiently in $$O(n)$$ time and $$O(1)$$ space. This approach demonstrates the power of combining basic techniques like the two-pointer method and iterative reversal to solve seemingly complex problems.\n\n---\n\nThank you for reading my post.\n\n##### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n##### \u2B50\uFE0F Related Video\n#206 Reverse Linked List\n\nhttps://youtu.be/9TsQmdRAxT8\n\n
['Linked List', 'Two Pointers', 'C++', 'Java', 'Python3']