题解 | #重排链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 
 * @return  void
 */
int getListLen(struct ListNode * head)
{
    int len = 0;
    while(head != NULL)
    {
        len++;
        head = head->next;
    }
    return len;
}

struct ListNode * getTail(struct ListNode * head)
{
    struct ListNode * preTail = head;
    while(preTail->next->next != NULL)
    {
        preTail = preTail->next;
    }
        
    return preTail;
}

void reorderList(struct ListNode* head ) {
    // write code here
    // 小于等于2个结点时，直接返回
    if(getListLen(head) <= 2)
    {
        return;
    }
    
    // 需要每次递归的时候，标记处来尾结点
    struct ListNode * tmp = getTail(head);
    struct ListNode * tail = tmp->next;
    tmp->next = NULL;
    reorderList(head->next);
    tail->next = head->next;
    head->next = tail;
    
}