143. Reorder List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* find_mid(ListNode* head) {
        if(head == nullptr) return head;

        ListNode* fast = head;
        ListNode* slow = head;

        while(fast->next and fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }

    ListNode* reverse(ListNode* head) {
        if(head == nullptr) return head;

        ListNode *prv = nullptr, *cur = head, *nxt = head;

        while(nxt != nullptr) {
            nxt = nxt->next;
            cur->next = prv;
            prv = cur;
            cur = nxt;
        }

        return prv;
    }

    void reorderList(ListNode* head) {
        if(head == nullptr) return;
        if(head->next == nullptr) return;

        ListNode* mid = find_mid(head);
        ListNode* rhead = reverse(mid->next);
        mid->next = nullptr;

        ListNode *itr = head, *ritr = rhead;
        ListNode *tmp = new ListNode();

        while(itr or ritr) {
            if(itr) {
                tmp->next = itr;
                itr = itr->next;
                tmp = tmp->next;
            }

            if(ritr) {
                tmp->next = ritr;
                ritr = ritr->next;
                tmp = tmp->next;
            }
        }
    }
};