/**
* 跟着算法走一遍就知道如何重新整理
**/
#include <iostream>
using namespace::std;

struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    //1,2,4,5 -> 1,4,2,5  1,2,3,4,5 -> 1,4,2,5,3
    int lengthOfList(ListNode* head){
        ListNode* p = head;
        int count = 0;
        while (p!=NULL) {
            p = p->next;
            count++;
        }
        return count;
    }

    /**
    * 翻转链表
    **/
    ListNode* reverseList(ListNode* head){
        ListNode* pre = head;
        ListNode* p = pre->next;
        ListNode* next = NULL;
        while (p!=NULL) {
            next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }
        head->next=NULL;
        return pre;
    }

    void reorderList(ListNode* head) {
        if (head==NULL||head->next==NULL) {
            return;
        }else{
            int n = lengthOfList(head);
            int half = n/2;
            if (n%2!=0) {
                half++;
            }
            ListNode* leftEnd = head;
            for (int i=0; i<half-1; i++) {
                leftEnd = leftEnd->next;
            }

            ListNode* rightStart = leftEnd->next;
            rightStart = reverseList(rightStart);

            leftEnd->next =NULL;
            ListNode* left = head;
            ListNode* right = rightStart;
            ListNode* next = NULL;

            //重新链接
            bool flag = true;
            while (right!=NULL) {
                if (flag) {
                    next = left->next;
                    left->next = right;
                    left = next;
                }else{
                    next = right->next;
                    right->next = left;
                    right = next;
                }
                flag = !flag;
            }
        }

    }
};
int main(int argc, const char * argv[]) {
    return 0;
}