/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

// 1. 使用快慢指针,找出链表的中心节点
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head, *slow = head;
    while(fast != NULL && fast->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

// 2. 通过递归反转链表
struct ListNode* reverseList(struct ListNode* head){
    if(!head || !head->next)
        return head;
    struct ListNode *L = malloc(sizeof(struct ListNode)), *p;
    L->next = NULL;
    while(head != NULL) {
        p = head->next;
        head->next = L->next;
        L->next = head;
        head = p;
    }
    return L->next;
}

// 3. 合并两个链表，将右链表插入到左链表
void mergeList(struct ListNode* left, struct ListNode* right){
    struct ListNode *leftTemp, *rightTemp;

    // merge的循环时候条件应为: 当右链表为空的时候,就结束循环
    // 原因是: 
    //     1.你取了中心节点的next为右链表的head, 那么两者的长度一定是  左链表 > 右链表
    //     2. 当原始链表为:  奇数 左链表=右链表+1 ; 偶数 左链表=右链表+2
    // 所以: 只用判断右链表的节点是否为空就可以了,而不用判断左链表. 左链表的next肯定有值.
    while(right != NULL){
        //1. 保存next节点
        leftTemp = left->next;
        rightTemp = right->next;

        // 2. 将右链表的第一个节点插入到左链表中
        // 左链表：1->2->3 右链表：5->4 
        // 合并后的左链表：1->5->2->3
        left->next = right;
        right->next = leftTemp;

        // 3. 移动left和right指针
        // 左链表变为：2->3 右链表变为：4
        left = leftTemp;
        right = rightTemp;
    }
}


void reorderList(struct ListNode* head){
    if(!head || !head->next)
        return head;

    // 1. 使用快慢指针,找出链表的中心节点。
    // 1->2->3->4->5,中心节点为3
    struct ListNode *middle = middleNode(head);
    
    // 2. 将原始链表按照中心链表分割为两个链表，并将右链表反转
    // 2.1 原始链表：1->2->3->4->5 左链表：1->2->3 右链表：4->5
    struct ListNode *left = head, *right = middle->next;
    middle->next = NULL;

    // 2.2 反转右链表
    //原始右链表：4->5 反转后：5->4
    right = reverseList(right);

    // 3. 合并两个链表，将右链表插入到左链表
    // 左链表：1->2->3 右链表：4->5 合并后：1->5->2->4->3
    mergeList(left, right);
}