Interview Approach | 4 Approaches
Subscribe to my channel\n\nBefore moving ahead, please read the yesterday\'s solution.\nI am reusing the 4th approach\n234. Palindrome Linked List\n\n# Approach
[Subscribe to my channel](https://www.youtube.com/channel/UCuxmikkhqbmBOUVxf-61hxw)\n\nBefore moving ahead, please read the yesterday\'s solution.\nI am reusing the 4th approach\n[234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/solutions/4908031/interview-approach-4-approach-list-stack-recursion-two-pointer-approach/)\n\n# Approach#1 ( Using List )\n\nSo as I told every Linked List problem can be done via array as well, I mena copy the content in array and solve it as it was an array and then update the list.\nHere also I could do the same, I will create array and then alternatively will replace values into linked list.\n\n![image.png](https://assets.leetcode.com/users/images/5b46c6b4-e64f-4a87-af3a-3bc9ed18201d_1711156638.7016938.png)\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        vector<int> list;\n        ListNode* curr = head;\n        while (curr != nullptr) {\n            list.push_back(curr->val);\n            curr = curr->next;\n        }\n\n        curr = head;\n        for (int i = 0; i < list.size(); ++i) {\n            curr->val = list[i%2 == 0 ? i/2 : list.size()-(i+1)/2];\n            curr = curr->next;\n        }\n    }\n};\n```\n```Java []\nclass Solution {\n    public void reorderList(ListNode head) {\n        List<Integer> list = new ArrayList();\n        ListNode curr = head;\n        while(curr != null) {\n            list.add(curr.val);\n            curr = curr.next;\n        }\n        for(int i=0;i<list.size();i++) {\n            head.val = list.get(i%2 == 0 ? i/2 : list.size()-(i+1)/2);\n            head = head.next;\n        }\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        list_values = []\n        curr = head\n        while curr:\n            list_values.append(curr.val)\n            curr = curr.next\n        \n        # Reorder the list using for loop\n        curr = head\n        for i in range(len(list_values)):\n            if i % 2 == 0:\n                curr.val = list_values[i // 2]\n            else:\n                curr.val = list_values[len(list_values) - (i + 1) // 2]\n            curr = curr.next\n```\n```JavaScript []\nvar reorderList = function(head) {\n    const list = [];\n    let curr = head;\n    while (curr !== null) {\n        list.push(curr.val);\n        curr = curr.next;\n    }\n\n    curr = head;\n    for (let i = 0; i < list.length; i++) {\n        if (i % 2 === 0) {\n            curr.val = list[Math.floor(i / 2)];\n        } else {\n            curr.val = list[list.length - Math.floor((i + 1) / 2)];\n        }\n        curr = curr.next;\n    }\n};\n```\n\n# Approach#2 ( Using Recursion )\nfor each node , find last node and re-arrange it and then move to next node.\n\n![image.png](https://assets.leetcode.com/users/images/8ecaeead-0faa-4e4b-a843-95108a1eaa49_1711156369.6611965.png)\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        helper(head);\n    }\n\n    ListNode* helper(ListNode* head) {\n        if (head == nullptr || head->next == nullptr) return head;\n        ListNode* last = head;\n        ListNode* prev = head;\n        while (last->next != nullptr) {\n            prev = last;\n            last = last->next;\n        }\n        prev->next = nullptr;\n        ListNode* next = head->next;\n        head->next = last;\n        last->next = helper(next);\n        return head;\n    }\n};\n```\n```Java []\nclass Solution {\n    public void reorderList(ListNode head) {\n        helper(head);\n    }\n\n    public ListNode helper(ListNode head) {\n        if(head == null || head.next == null) return head;\n        ListNode last = head;\n        ListNode prev = head;\n        while(last.next != null) {\n            prev = last;\n            last = last.next;\n        }\n        prev.next = null;\n        ListNode next = head.next;\n        head.next = last;\n        last.next = solve(next);\n        return head;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        self.helper(head)\n\n    def helper(self, head: Optional[ListNode]) -> ListNode:\n        if head is None or head.next is None:\n            return head\n        last = head\n        prev = head\n        while last.next:\n            prev = last\n            last = last.next\n        prev.next = None\n        next_node = head.next\n        head.next = last\n        last.next = self.helper(next_node)\n        return head\n```\n```Javascript []\nvar reorderList = function(head) {\n    helper(head);\n};\n\nvar helper = function(head) {\n    if (head === null || head.next === null) {\n        return head;\n    }\n    let last = head;\n    let prev = head;\n    while (last.next !== null) {\n        prev = last;\n        last = last.next;\n    }\n    prev.next = null;\n    const next = head.next;\n    head.next = last;\n    last.next = helper(next);\n    return head;\n};\n```\n\n# Approach#3 ( Recursion - Only Smart A** can understand )\nJust think of like you know that end of the linked list is always middle and next middle. then we can append at the start previous of middle with next of next middle and so on.\n\nI think you didn\'t understand this, let me draw for you.\nDraft: ( I will draw here and will update code for other languages , till then you can try to think like how it\'s possible , Take your time. )\n\n![image.png](https://assets.leetcode.com/users/images/def334fb-d660-469f-8642-be91d30747ba_1711165955.4785228.png)\n![image.png](https://assets.leetcode.com/users/images/e42ec9af-4dbd-406e-9c82-084e9b0810d1_1711165910.3344858.png)\n\n# Code\n```Java []\nclass Solution {\n    public void reorderList(ListNode head) {\n        helper(head, head.next);\n    }\n\n    public ListNode[] helper(ListNode slow, ListNode fast) {\n        if(fast == null || fast.next == null) \n            return new ListNode[]{slow, fast == null ? slow : slow.next};\n        ListNode[] ret = helper(slow.next, fast.next.next);\n        ListNode next = ret[1].next;\n        if(ret[1].next != null) ret[1].next = ret[1].next.next;\n        slow.next = next;\n        if(next != null) next.next = ret[0];\n        return new ListNode[]{slow, ret[1]};\n    }\n}\n```\n\n# Approach#4 ( Like Palindrome Linked List )\n<!-- Describe your first thoughts on how to solve this problem. -->\nSo Basically\nL0 -> LN -> L1 -> LN-1 .....\nDid you find any similarity between palindrome linked list and this one, if yes congratulations you made this problem easy.\n\n```Steps []\n- first find middle node\n- reverse the second half\n- now merge first and second half alternatively\n```\n\n![image.png](https://assets.leetcode.com/users/images/c744f01f-2d58-412f-8ebd-6870edb6ba00_1711153504.1462193.png)\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    ListNode* reverse(ListNode* head) {\n        ListNode* prev = nullptr;\n        ListNode* curr = head;\n        while (curr != nullptr) {\n            ListNode* next = curr->next;\n            curr->next = prev;\n            prev = curr;\n            curr = next;\n        }\n        return prev;\n    }\n\n    void reorderList(ListNode* head) {\n        if (head == nullptr) return;\n\n        ListNode* slow = head;\n        ListNode* fast = head->next;\n        while (fast != nullptr && fast->next != nullptr) {\n            slow = slow->next;\n            fast = fast->next->next;\n        }\n\n        ListNode* rev = reverse(slow->next);\n        slow->next = nullptr;\n\n        while (rev != nullptr) {\n            ListNode* headNext = head->next;\n            ListNode* revNext = rev->next;\n            head->next = rev;\n            rev->next = headNext;\n            head = headNext;\n            rev = revNext;\n        }\n    }\n};\n```\n```Java []\nclass Solution {\n    public ListNode reverse(ListNode head) {\n        ListNode prev = null;\n        ListNode curr = head;\n        while(curr != null) {\n            ListNode next = curr.next;\n            curr.next = prev;\n            prev = curr;\n            curr = next;\n        }\n        return prev;\n    }\n\n    public void reorderList(ListNode head) {\n        ListNode slow = head;\n        ListNode fast = head.next;\n        while(fast != null && fast.next != null) {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n        ListNode rev = reverse(slow.next); // reverse second list\n        slow.next = null;\n\n        // now add node one by one\n        while(rev != null) {\n            ListNode headNext = head.next;\n            ListNode revNext = rev.next;\n            head.next = rev;\n            rev.next = headNext;\n            head = headNext;\n            rev = revNext;\n        }\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def reverse(self, head: ListNode) -> ListNode:\n        prev = None\n        curr = head\n        while curr:\n            next_temp = curr.next\n            curr.next = prev\n            prev = curr\n            curr = next_temp\n        return prev\n\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        if head is None:\n            return\n\n        # Find the middle of the list\n        slow = head\n        fast = head.next\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n\n        # Reverse the second half\n        rev = self.reverse(slow.next)\n        slow.next = None\n\n        # Reorder one by one\n        while rev:\n            head_next = head.next\n            rev_next = rev.next\n            head.next = rev\n            rev.next = head_next\n            head = head_next\n            rev = rev_next\n```\n```Javascript []\nvar reverse = function(head) {\n    let prev = null;\n    let curr = head;\n    while (curr !== null) {\n        let nextTemp = curr.next;\n        curr.next = prev;\n        prev = curr;\n        curr = nextTemp;\n    }\n    return prev;\n}\n\nvar reorderList = function(head) {\n    if (!head) return;\n\n    let slow = head;\n    let fast = head.next;\n    while (fast && fast.next) {\n        slow = slow.next;\n        fast = fast.next.next;\n    }\n\n    let rev = reverse(slow.next);\n    slow.next = null;\n\n    while (rev) {\n        let headNext = head.next;\n        let revNext = rev.next;\n        head.next = rev;\n        rev.next = headNext;\n        head = headNext;\n        rev = revNext;\n    }\n};\n```\n\nIf you like this post, please upvote it.
['C++', 'Java', 'Python3', 'JavaScript']