🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n---\n\n\n\n# Intuition\nTo reorder a linked list, the goal is to place the last node after the first, then the second-to-last node after the second, and so 
![image.png](https://assets.leetcode.com/users/images/ca510a8e-c456-4aa2-aae1-024228534c15_1733395244.233278.png)\n\n---\n\n\n\n# Intuition\nTo reorder a linked list, the goal is to place the last node after the first, then the second-to-last node after the second, and so on. This can be done by splitting the list into two halves, reversing the second half, and merging them alternately. The key insight is that we only need pointers to reorder the list without creating additional structures.\n\n---\n\n# Approach\n1. **Find the middle of the list:**  \n   Using the slow and fast pointer technique, find the midpoint of the linked list.\n   \n2. **Reverse the second half:**  \n   Reverse the second half of the list starting from the node after the midpoint.\n   \n3. **Merge the two halves:**  \n   Merge the first half and the reversed second half alternately.\n\n4. **Ensure correctness in edge cases:**  \n   Handle cases like an empty list or a list with only one node, which don\u2019t require reordering.\n\n---\n\n# Complexity\n- **Time complexity:**  \n  $$O(n)$$ where \\(n\\) is the number of nodes in the linked list. Finding the middle, reversing the second half, and merging are all linear operations.\n  \n- **Space complexity:**  \n  $$O(1)$$ as the reordering is done in-place with no additional data structures.\n\n---\n\n\n```dart []\n/**\n * Definition for singly-linked list.\n * class ListNode {\n *   int val;\n *   ListNode? next;\n *   ListNode([this.val = 0, this.next]);\n * }\n */\nclass Solution {\n  void reorderList(ListNode? head) {\n    if (head == null || head.next == 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: Disconnect the first and second halves\n    ListNode? secondHalf = slow?.next;\n    slow?.next = null;\n\n    // Step 3: Reverse the second half\n    secondHalf = _reverse(secondHalf);\n\n    // Step 4: Merge the two halves\n    ListNode? firstHalf = head;\n    while (firstHalf != null && secondHalf != null) {\n      ListNode? temp1 = firstHalf.next;\n      ListNode? temp2 = secondHalf.next;\n\n      firstHalf.next = secondHalf;\n      secondHalf.next = temp1;\n\n      firstHalf = temp1;\n      secondHalf = temp2;\n    }\n  }\n\n  // Helper function to reverse a linked list\n  ListNode? _reverse(ListNode? head) {\n    ListNode? prev = null;\n    while (head != null) {\n      ListNode? next = head.next;\n      head.next = prev;\n      prev = head;\n      head = next;\n    }\n    return prev;\n  }\n}\n```\n\n\n```python []\nclass Solution:\n    def reorderList(self, head):\n        if not head or not head.next:\n            return\n        \n        # Step 1: Find the middle of the list\n        slow, fast = head, head\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n        \n        # Step 2: Reverse the second half\n        prev, curr = None, slow.next\n        slow.next = None  # Disconnect the two halves\n        while curr:\n            temp = curr.next\n            curr.next = prev\n            prev = curr\n            curr = temp\n        \n        # Step 3: Merge the two halves\n        first, second = head, prev\n        while second:\n            temp1, temp2 = first.next, second.next\n            first.next = second\n            second.next = temp1\n            first, second = temp1, temp2\n```\n\n\n```javascript []\nvar reorderList = function(head) {\n    if (!head || !head.next) 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\n    let secondHalf = slow.next;\n    slow.next = null; // Disconnect the two halves\n    let prev = null;\n    while (secondHalf) {\n        let temp = secondHalf.next;\n        secondHalf.next = prev;\n        prev = secondHalf;\n        secondHalf = temp;\n    }\n\n    // Step 3: Merge the two halves\n    let firstHalf = head;\n    while (prev) {\n        let temp1 = firstHalf.next;\n        let temp2 = prev.next;\n        firstHalf.next = prev;\n        prev.next = temp1;\n        firstHalf = temp1;\n        prev = temp2;\n    }\n};\n```\n\n\n```java []\nclass Solution {\n    public void reorderList(ListNode head) {\n        if (head == null || head.next == 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\n        ListNode secondHalf = slow.next;\n        slow.next = null;\n        ListNode prev = null;\n        while (secondHalf != null) {\n            ListNode temp = secondHalf.next;\n            secondHalf.next = prev;\n            prev = secondHalf;\n            secondHalf = temp;\n        }\n\n        // Step 3: Merge the two halves\n        ListNode firstHalf = head;\n        while (prev != null) {\n            ListNode temp1 = firstHalf.next;\n            ListNode temp2 = prev.next;\n            firstHalf.next = prev;\n            prev.next = temp1;\n            firstHalf = temp1;\n            prev = temp2;\n        }\n    }\n}\n```\n\n\n```cpp []\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        if (!head || !head->next) return;\n\n        // Step 1: Find the middle of the list\n        ListNode* 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\n        ListNode* secondHalf = slow->next;\n        slow->next = nullptr;\n        ListNode* prev = nullptr;\n        while (secondHalf) {\n            ListNode* temp = secondHalf->next;\n            secondHalf->next = prev;\n            prev = secondHalf;\n            secondHalf = temp;\n        }\n\n        // Step 3: Merge the two halves\n        ListNode* firstHalf = head;\n        while (prev) {\n            ListNode* temp1 = firstHalf->next;\n            ListNode* temp2 = prev->next;\n            firstHalf->next = prev;\n            prev->next = temp1;\n            firstHalf = temp1;\n            prev = temp2;\n        }\n    }\n};\n```\n\n\n```go []\nfunc reorderList(head *ListNode) {\n    if head == nil || head.Next == nil {\n        return\n    }\n\n    // Step 1: Find the middle of the list\n    slow, fast := head, head\n    for fast != nil && fast.Next != nil {\n        slow = slow.Next\n        fast = fast.Next.Next\n    }\n\n    // Step 2: Reverse the second half\n    secondHalf := slow.Next\n    slow.Next = nil\n    var prev *ListNode\n    for secondHalf != nil {\n        temp := secondHalf.Next\n        secondHalf.Next = prev\n        prev = secondHalf\n        secondHalf = temp\n    }\n\n    // Step 3: Merge the two halves\n    firstHalf := head\n    for prev != nil {\n        temp1 := firstHalf.Next\n        temp2 := prev.Next\n        firstHalf.Next = prev\n        prev.Next = temp1\n        firstHalf = temp1\n        prev = temp2\n    }\n}\n```\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Linked List', 'Two Pointers', 'C', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']