Reorder List Solutions in C++

// Source : https://oj.leetcode.com/problems/reorder-list/
// Author : Hao Chen
// Date   : 2014-06-17



#include <stdio.h>
#include <stdlib.h>
/**
 * Definition for singly-linked list.
 */
class ListNode {
public:
    int val;
    ListNode *next;
    ListNode():val(0), next(NULL) {}
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    void reorderList(ListNode *head) {
        ListNode *pMid = findMidPos(head);
        pMid = reverseList(pMid);
        head = Merge(head, pMid);
    }
    
private:
    ListNode* findMidPos(ListNode *head){

        ListNode *p1, *p2, *p=NULL;
        p1 = p2 = head;
        
        while(p1!=NULL && p2!=NULL && p2->next!=NULL){
            p = p1;
            p1 = p1->next;
            p2 = p2->next->next;
        }

        if(p!=NULL){
            p->next = NULL;
        }
        
        return p1;
    }
    
    ListNode* reverseList(ListNode *head){
        ListNode* h = NULL;
        ListNode *p;
        while (head!=NULL){
            p = head;
            head = head->next;
            p->next = h;
            h = p;
        }
        return h;
    }
    
    ListNode* Merge(ListNode *h1, ListNode* h2) {
        ListNode *p1=h1, *p2=h2, *p1nxt, *p2nxt;
        while(p1!=NULL && p2!=NULL){
            p1nxt = p1->next;
            p2nxt = p2->next;
            
            p1->next = p2;
            p2->next = p1nxt;
            
            if (p1nxt==NULL){
                p2->next = p2nxt;
                break;
            }
            p1=p1nxt;
            p2=p2nxt;
        }
    }
};

void printList(ListNode *h){
    while(h!=NULL){
        printf("%d->", h->val);
        h = h->next;
    }
    printf("nil\n");
}

int main(int argc, char** argv)
{
    int size = atoi(argv[1]);
    ListNode* n = new ListNode[size] ;

    for(int i=0; i<size; i++){
        n[i].val = i;
        if( i+1 < size) {
            n[i].next = &n[i+1];
        }
    }


    Solution s;
    s.reorderList(&n[0]);
    printList(&n[0]);
    
    
    
    return 0;
}

/// Source : https://leetcode.com/problems/reorder-list/
/// Author : liuyubobobo
/// Time   : 2019-08-30

#include <iostream>

using namespace std;


/// Simulations
/// Time Complexity: O(n)
/// Space Complexity: O(1)


/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


class Solution {
public:
    void reorderList(ListNode* head) {

        if(!head || !head->next) return;

        ListNode* slow = head, *fast = head;
        while(fast->next && fast->next->next)
            slow = slow->next, fast = fast->next, fast = fast->next;

        ListNode* head1 = head, *head2 = slow->next;
        slow->next = NULL;
        head2 = reverse(head2);

        ListNode* dummyHead = new ListNode(-1);
        ListNode* cur= dummyHead, *cur1 = head1, *cur2 = head2;
        for(int i = 0; cur1 || cur2; i ++)
            if(i % 2 == 0) cur->next = cur1, cur = cur->next, cur1 = cur1->next;
            else cur->next = cur2, cur = cur->next, cur2 = cur2->next;
        head = dummyHead->next;
    }

private:
    ListNode* reverse(ListNode* node){

        if(!node->next) return node;
        ListNode* ret = reverse(node->next);
        node->next->next = node;
        node->next = NULL;
        return ret;
    }
};


int main() {

    return 0;
}