C++ O(n) Time & O(1) Space | Iterative approach.
The idea here is to update our input list by reversing the second half of the list.\nWe find the middle of the List, and call the reverseList(), which returns b
The idea here is to update our input list by reversing the second half of the list.\nWe find the middle of the List, and call the ```reverseList()```, which returns back the head from the right side. After this, we will have two pointers, one pointing to the input head node (on the left) and the new head (on the right side) with the second half reversed. [**O(n)** time]\n```c++\n\t 1->2->3->4->null;\n\t //After rearrangements\n\t (head1) 1->2-> null <-3<-4 (head2)\n```\n\nNow we can alternatively pick nodes and update the links to create the required list and finally update our input head.  [**O(n)** time.]\n```c++\nListNode *reverseList(ListNode *h){\n        ListNode *r = nullptr, *q = nullptr, *p = h;\n        do{\n            r = q;\n            q = p;\n            p = p->next;\n            q->next = r;\n        }while(p);\n        return q;\n    }\n    void reorderList(ListNode* head) {\n        if(!head || !head->next) return;\n        \n        ListNode *ptr1 = head, *ptr2 = head;\n        while(ptr2 and ptr2->next){\n            ptr1 = ptr1->next;\n            ptr2 = ptr2->next->next;\n        }\n\n        ptr2 = reverseList(ptr1);\n        ptr1 = head; \n        \n        ListNode *header = new ListNode(-1);\n        ListNode *p = header;\n\t\t// mutex will strictly iterate between 0 & 1 to pick nodes.\n        int mutex = 1; \n        while(ptr1 and ptr2){\n            if(mutex){\n                p->next = ptr1;\n                p = ptr1;\n                ptr1 = ptr1->next;\n                p->next = nullptr;\n            }else{\n                p->next = ptr2;\n                p = ptr2;\n                ptr2 = ptr2->next;\n                p->next =nullptr;\n            }\n            mutex = (1 + mutex)%2;\n        }\n\t\t//update the input head node and return.\n        head = header->next;\n        return;\n    }\n\n```\n
[]