C++ EASY TO SOLVE || Beginner Friendly with detailed explanation and dry run
Intuition:-\nAfter reading the question we got the gist that we need to reform the linkedlist in the manner such as\nfirstnode->lastnode->secondnode->penultimat
**Intuition:-**\nAfter reading the question we got the gist that we need to reform the linkedlist in the manner such as\n`firstnode->lastnode->secondnode->penultimate node->third node->3rd last node ............` .\nSo there are two ways that comes to my mind while thinking about a approach . Those are ,\n\n**1. Brute Force :-**\n* In this we will first traverse to penultimate node and then start relinking each node .\n\n**2.** **Two pointer approach[sometimes referred as Tortoise and hare method]:-**\n* We will have two pointers 1st pointer moving at speed of 1node and 2nd pointer moving at speed of twice the node. So basically one is moving at double speed and thus when it will be finished, the other has to be midway) and possibly adjusting it with lists of even length. This creates two halfs of linkedlist\n* Then we reverse the second list and Finally we merge these two lists.\n\n**Brute-Force Algorithm:-**\n1. First some base cases that we need to take care i.e if the linked list has zero,one or two elements just return it \n2. Now next we need to find the penultimate node, so after finding it we can start the relinking process\n3. Now start the relinking process as 1st node with last node ,2nd node with penultimate node, 3rd node with 3rd last node ......\n4. Now repeat 2nd and 3rd steps.\n\n**Let\'s have a dy run before starting the code:-**\n![image](https://assets.leetcode.com/users/images/a436d8ab-0868-4990-9214-74fc5ba59992_1640143095.7645688.jpeg)\n\n\n**Brute-Force code-:**\n```\n//Upvote  and Comment\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        //base case i.e if the linked list has zero,one or two elments just return it\n        if(!head || !head->next || !head->next->next) return;\n        \n        //Find the penultimate node i.e second last node of the linkedlist\n        ListNode* penultimate = head;\n        while (penultimate->next->next) penultimate = penultimate->next;\n        \n        // Link the penultimate with the second element\n        penultimate->next->next = head->next;\n        head->next = penultimate->next;\n        \n        //Again set the penultimate to the the last \n        penultimate->next = NULL;\n        \n        // Do the above steps rcursive\n        reorderList(head->next->next);\n    }\n};\n```\n.\n\n\n**Two pointer Approach [Tortoise and Hare method]:-**\n*This approach is much faster and efficient in terms of Time and Space Complexity the only drawback is that it looks a little bit lengthy but trust me it\'s easy to understand*.\n\n**Two pointer Approach Algorithm:**\n1. First let\'s take two pointers name it as `half` and `temp` . `temp ` is faster than `half` by 1. \n2. When `temp` reaches the end of linkedlsit `half` reaches the middle element .So this is how the linkedlist will get divided in two halfes as the center will become a dividing node .\n3. Now reverse the second half . \n4. After reversing the second half, merge the first half and second half\n\n**Let\'s have a dy run before starting the code:-**\nLet\'s take the same example as above:\n```\nLinked list:[1,2,3,4,5]\n* search for the central element, which will be three in our case\n* split the list in two halfes that will be [1,2,3] and [4,5]\n* Now reverse the second half that will be [5,4]\n* Now merge both the halfes \n[1,2,3]\n\t[5,4]\n=>[1,5,2,4,3]\n\n**See told you it\'s easy to understand**\n```\n\n\n**Two pointer Approach Code:-**\n```\n//Upvote and Comment\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // base case : linkedlist is empty\n        if (!head) return;\n        \n        // finding the middle with the help of two pointer approach\n        ListNode *tmp = head, *half = head, *prev = NULL;\n        while (tmp->next && tmp->next->next) {\n            tmp = tmp->next->next;\n            half = half->next;\n        }\n        \n        // adding one bit in case of lists with even length\n        if (tmp->next) half = half->next;\n        \n        // Now reverse the second half\n        while (half) {\n            tmp = half->next;\n            half->next = prev;\n            prev = half;\n            half = tmp;\n        }\n        half = prev;\n        \n        // After reversing the second half, let\'s merge both the halfes\n        while (head && half) {\n            tmp = head->next;\n            prev = half->next;\n            head->next = half;\n            half->next = tmp;\n            head = tmp;\n            half = prev;\n        }\n        \n        // Base case : closing when we had even length arrays\n        if (head && head->next) head->next->next = NULL;\n    }\n};\n```\n**Time Complexity :** *`O(N) [ O(N) to find mid of list, O(N/2) to reverse the 2nd half and in the end O(N) for relinking purpose  ]`*\n**Space Complexity :** *`O(1) [intermediate state variables are the only thing  that we used]`*\n\n***\n\n
['Linked List', 'Two Pointers', 'Recursion', 'C', 'C++']