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:
    void reorderList(ListNode* head) {
        if ((!head) || (!head->next) || (!head->next->next))
            return; // Edge cases
        
        stack<ListNode*> my_stack;
        ListNode* ptr = head;
        int size = 0;
        while (ptr != NULL) // Put all nodes in stack
        {
            my_stack.push(ptr);
            size++;
            ptr = ptr->next;
        }
        
        ListNode* pptr = head;
        for (int j=0; j<size/2; j++) // Between every two nodes insert the one in the top of the stack
        {
            ListNode *element = my_stack.top();
            my_stack.pop();
            element->next = pptr->next;
            pptr->next = element;
            pptr = pptr->next->next;
        }
        pptr->next = NULL;
//         if(head==NULL || head->next==NULL)
//             return;
//         ListNode *fast=head,*slow=head;
//         while(fast!=NULL&&fast->next!=NULL){
//             slow=slow->next;
//             fast=fast->next->next;
//         }
        
//         ListNode *curr=slow->next;
//         slow->next=NULL;
//         while(curr!=NULL){
//             ListNode *next=curr->next;
//             curr->next=slow->next;
//             slow->next=curr;
//             curr=next;
//         }
        
//         ListNode *left=head,*right=slow->next;
//         while(right!=NULL ){
//             slow->next=right->next;
//             right->next=left->next;
//             left->next=right;
//             left=right->next;
//             right=slow->next;
//         }
    }
};