Easy C++ || beats 99.47% || 3 Easy Steps || TC: O(n) , SC: O(1) || Explanation With Diagram
Intuition\nSee picture I Uploaded below. Its 80% observation and 20% code.\nIf you have done another problem where we reverse a linked list, CONGRATULATIONS, yo
# Intuition\nSee picture I Uploaded below. Its 80% observation and 20% code.\nIf you have done another problem where we reverse a linked list, CONGRATULATIONS, you are left with 10% of code.\n# Approach\nSTEP 1: Break the list in 2 halves using SLOW and FAST pointer.\nSTEP 2: Reverse the 2nd part.\nSTEP 3: JOIN the corresponding element (eg: 1st and 1st, 2nd and 2nd). See picutre i uploaded.\n**PLS UPVOTE THIS POST, I NEED MY FIRST BADGE**\n![f56908ec-f83f-4d90-b7f4-c51e6f9dcc4a.jfif](https://assets.leetcode.com/users/images/29e7a661-7529-403c-a972-999d0785480f_1711172577.1442623.jpeg)\n\n\n\n\n# Complexity\n- Time complexity:\n**O(n)**\n- Space complexity:\n**O(1)**\n\n# Code\n```\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 {\nprivate:\n    ListNode* reverseLL(ListNode* head){\n         // just a code for reversing a linked list\n        if (!head || !head->next) return head;\n        ListNode * prev = nullptr;\n        ListNode * next = nullptr;\n        ListNode * temp = head;\n\n        while (temp){\n            next = temp->next;\n            temp->next = prev;\n            prev = temp;\n            temp = next;\n        }\n        return prev;\n    }\npublic:\n    void reorderList(ListNode* head) {\n        // step 1 find the start of second half of ll\n        ListNode * slow = head;\n        ListNode * fast = head;\n        ListNode* head2 = nullptr;\n\n        while (fast->next && fast->next->next){\n            slow = slow->next;\n            fast = fast->next ->next;\n        }\n        // step2: reverse the second half\n        head2 = reverseLL(slow->next);\n\n        // disconnect both halves\n        slow->next =nullptr;\n \n        // 3 finally point the ith element of each part\n        ListNode * a = head;\n        ListNode * b = head2;\n\n        while (a && b){\n            ListNode * a2 = a->next;\n            ListNode * b2 = b->next;\n            b->next = a2;\n            a->next = b;\n            if (a2 && !b2) {\n                b->next = a2;\n                return;\n            }\n            a=a2; b=b2;\n        }   \n    }\n};\n\n```
['Linked List', 'C++']