Reverse Second Half And Merge the Lists | | Two-Pointer | | C++ | | Java | | Python3 | | ✅✅✅🔥🔥🔥
\n\n Here\'s a response that directly uses the variables from the provided code:\n\nIntuition:\n\n- We\'ll rearrange the linked list using three key steps: find
\n![image.png](https://assets.leetcode.com/users/images/22578f7b-c72a-4207-8208-dd1ce875e257_1711158308.9214664.png)\n **Here\'s a response that directly uses the variables from the provided code:**\n\n**Intuition:**\n\n- We\'ll rearrange the linked list using three key steps: finding the middle node, reversing the second half, and merging the two halves in an alternating pattern.\n\n**Approach:**\n\n1. **Find the Middle Node:**\n   - Initialize `slow` and `fast` pointers to `head`.\n   - While `fast` and `fast->next` exist, move `slow` one step and `fast` two steps.\n   - `slow` will now point to the middle node.\n\n2. **Reverse the Second Half:**\n   - Call `reverse(slow)` to reverse the list starting from `slow`.\n   - This returns the new head of the reversed portion (`list2`).\n\n3. **Merge the Two Halves:**\n   - Keep a `prev` pointer to set `prev->next` to `NULL` later, marking the end of the first half.\n   - Iterate through `list1` and `list2`:\n     - Store `list1->next` as `nextNode`.\n     - Connect `list1->next` to `list2`.\n     - Move `list1` to `nextNode`.\n     - Move `list2` to `list2->next`.\n\n**Time Complexity:**\n\n- Finding middle: O(n)\n- Reversing: O(n/2) ~ O(n)\n- Merging: O(n)\n- Total: O(3n) ~ O(n)\n\n**Space Complexity:**\n\n- Extra pointers: O(1)\n- Recursive `reverse` call stack: O(n) in worst-case (extremely long lists), but practically considered O(1).\n\n```C++ []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* reverse(ListNode *head){\n        if(!head) return NULL;\n        ListNode *prev = NULL;\n        ListNode *curr = head;\n        ListNode *nextNode = NULL;\n        while(curr){\n            nextNode = curr->next;\n            curr->next = prev;\n            prev = curr;\n            curr = nextNode;\n        }\n        return prev;\n    }\n\n    void merge(ListNode *list1, ListNode *list2){\n        while(list2) {\n            ListNode  *nextNode = list1->next;\n            list1->next = list2;\n            list1 = list2;\n            list2 = nextNode;\n\n        }\n\n    }\n    void reorderList(ListNode* head) {\n        if(!head || !head->next) return;\n        ListNode *slow = head;\n        ListNode *fast = head;\n        ListNode *prev = head;\n        while(fast && fast->next){\n            prev = slow;\n            fast = fast->next->next;\n            slow = slow->next;\n        }\n        prev->next = NULL;\n        ListNode *list1 = head;\n        ListNode *list2 = reverse(slow);\n        merge(list1,list2);\n    }\n};\n```\n```Java []\n/*class ListNode {\n    int val;\n    ListNode next;\n    ListNode() {}\n    ListNode(int val) { this.val = val; }\n    ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n}*/\n\nclass Solution {\n    public ListNode reverse(ListNode head) {\n        if (head == null) return null;\n        ListNode prev = null;\n        ListNode curr = head;\n        ListNode nextNode = null;\n        while (curr != null) {\n            nextNode = curr.next;\n            curr.next = prev;\n            prev = curr;\n            curr = nextNode;\n        }\n        return prev;\n    }\n\n    public void merge(ListNode list1, ListNode list2) {\n        while (list2 != null) {\n            ListNode nextNode = list1.next;\n            list1.next = list2;\n            list1 = list2;\n            list2 = nextNode;\n        }\n    }\n\n    public void reorderList(ListNode head) {\n        if (head == null || head.next == null) return;\n        ListNode slow = head;\n        ListNode fast = head;\n        ListNode prev = head;\n        while (fast != null && fast.next != null) {\n            prev = slow;\n            fast = fast.next.next;\n            slow = slow.next;\n        }\n        prev.next = null;\n        ListNode list1 = head;\n        ListNode list2 = reverse(slow);\n        merge(list1, list2);\n    }\n}\n\n```\n```Python3 []\nclass ListNode:\n    def __init__(self, val=0, next=None):\n        self.val = val\n        self.next = next\n\nclass Solution:\n    def reverse(self, head):\n        if not head:\n            return None\n        prev = None\n        curr = head\n        nextNode = None\n        while curr:\n            nextNode = curr.next\n            curr.next = prev\n            prev = curr\n            curr = nextNode\n        return prev\n\n    def merge(self, list1, list2):\n        while list2:\n            nextNode = list1.next\n            list1.next = list2\n            list1 = list2\n            list2 = nextNode\n\n    def reorderList(self, head):\n        if not head or not head.next:\n            return\n        slow = head\n        fast = head\n        prev = head\n        while fast and fast.next:\n            prev = slow\n            fast = fast.next.next\n            slow = slow.next\n        prev.next = None\n        list1 = head\n        list2 = self.reverse(slow)\n        self.merge(list1, list2)\n\n```\n\n```JavaScript []\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val === undefined ? 0 : val)\n *     this.next = (next === undefined ? null : next)\n * }\n */\n/**\n * @param {ListNode} head\n * @return {void} Do not return anything, modify head in-place instead.\n */\nvar reorderList = function(head) {\n    if (!head || !head.next) return;\n    \n    // Find the middle of the linked list\n    let slow = head;\n    let fast = head;\n    while (fast.next && fast.next.next) {\n        slow = slow.next;\n        fast = fast.next.next;\n    }\n    \n    // Reverse the second half of the linked list\n    let prev = null;\n    let curr = slow.next;\n    while (curr) {\n        let nextNode = curr.next;\n        curr.next = prev;\n        prev = curr;\n        curr = nextNode;\n    }\n    slow.next = null;\n    \n    // Merge the two halves\n    let p1 = head;\n    let p2 = prev;\n    while (p1 && p2) {\n        let nextP1 = p1.next;\n        let nextP2 = p2.next;\n        p1.next = p2;\n        p2.next = nextP1;\n        p1 = nextP1;\n        p2 = nextP2;\n    }\n};\n\n```\n\n\n\n**Dry Run:**\n\n**Example:** `head = [1, 2, 3, 4]`\n\n1. **Find Middle:**\n   - `slow` = 1, `fast` = 4 (after loop)\n   - Middle node: `slow = 2`\n\n2. **Reverse:**\n   - `list2` = `reverse(2)` = `4 -> 3 -> 2`\n\n3. **Merge:**\n   - `list1` = `1 -> 2 -> 3 -> 4`, `list2` = `4 -> 3 -> 2`\n   - Iteration 1: `list1 = 1 -> 4`, `list2 = 3 -> 2`, `prev->next = NULL`\n   - Iteration 2: `list1 = 4 -> 3`, `list2 = 2`\n   - Final list: `1 -> 4 -> 2 -> 3`\n
['Linked List', 'Two Pointers', 'C++', 'Java', 'Python3', 'JavaScript']