题解 | #重排链表#

核心思想

• 递归
• 每入栈，标记出来尾结点，且断开其父节点
• 入栈是往中间走
• 出栈是从中间开始排序，往两边走

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

/**
 * 
 * @param head ListNode类 
 * @return  void
 */
// static struct ListNode * oldHead = NULL;
// static struct ListNode * curl = NULL;

// struct ListNode * reverse(struct ListNode * head)
// {
//     // 尾结点条件
//     static int len = 1;
//     len++;
//     if(head->next->next == NULL)
//     {
//         return head;
//     }
    
//     struct ListNode * tail = NULL;
//     tail = reverse(head->next);
//     if(len < (len/2 -1))
//     {
//         return head;
//     }
//     tail->next->next = curl->next;
//     curl->next = tail->next;
//     tail->next = NULL;
//     curl = curl->next->next;
//     // 找到尾结点后，把尾结点插入到头结点后，且头结点curl预先指向下一个结点
    
//     return head;
// }

void reorderList(struct ListNode* head ) {
    // write code here
    if(head == NULL)
    {
        return;
    }
    
    if(head->next == NULL || head->next->next == NULL)
    {
        return;
    }
    
    struct ListNode * curl = head;
    while(curl->next->next != NULL)
    {
        curl = curl->next;
    }
    
    struct ListNode * tail = curl->next;
    curl->next = NULL;
    reorderList(head->next);
    tail->next = head->next;
      
    head->next = tail;
}