struct ListNode* midList(struct ListNode* head)
{
   struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

void mergeList(struct ListNode* l1,struct ListNode* l2)
{
   struct ListNode* temp1;
    struct ListNode* temp2;
    while (l2 != NULL) {
        temp1 = l1->next;
        temp2 = l2->next;

        l1->next = l2;
        l1 = temp1;

        l2->next = l1;
        l2 = temp2;
    }
}

struct ListNode* reserveList(struct ListNode* head)
{
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while (cur != NULL) {
        struct ListNode* nextTemp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nextTemp;
    }
    return pre;
}

void reorderList(struct ListNode* head){
    struct ListNode* mid = midList(head);
    struct ListNode* L1 = head;
    struct ListNode* L2 = mid->next;
    mid->next = NULL;
    L2 = reserveList(L2);
    mergeList(L1,L2);
}