题解 | #重排链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return  void
 */

void reorderList(struct ListNode* head ) {
    
    int nodeNum = 0;
    int i = 0;
    struct ListNode *temp = head;
    struct ListNode **nodeArry = NULL;

    if ((head == NULL) || (head->next == NULL)){
        return;
    }

    while (temp != NULL){
        nodeNum++;
        nodeArry = (struct ListNode **)realloc(nodeArry, (nodeNum * sizeof(struct ListNode *)));
        nodeArry[(nodeNum - 1)] = temp;
        temp = temp->next;
    }

    for (i = nodeNum - 1; i >= nodeNum / 2; i--){
        nodeArry[nodeNum - 1 - i]->next = nodeArry[i];
        nodeArry[i]->next = nodeArry[nodeNum - i];
    }
    nodeArry[i + 1]->next = NULL;
}