题解 | #重排链表#

/***
* 
	递归思路：建立左右双指针，每次递归找到最后一个节点插入双指针中间，然后移动双指针
*
***/
void insertNode(struct ListNode *src, struct ListNode *dst)
{
    src->next = dst->next;
    dst->next = src;
}

void reorderList(struct ListNode* head ) {
    if(!head || !head->next)
    {
        return;
    }
    struct ListNode *left = head;
    struct ListNode *right = head->next;
    struct ListNode *pre_end = head;
    struct ListNode *end = pre_end->next;
    while (pre_end->next->next) {
        pre_end = pre_end->next;
        end = pre_end->next;
    }
    if(left==pre_end || !end)
    {
        return;
    }
    insertNode(end, left);
    pre_end->next = NULL;
    
    left = right;
    right = right->next;
    reorderList(left);
}