题解 | #重排链表#

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

/**
 * 
 * @param head ListNode类 
 * @return  void
 */
void reorderList(struct ListNode* head ) {
    // write code here
    int run_tim=0;//除1之外的，剩余的数/2就等于运行次数 如1 2 3 4 运行次数为1 只是 2对 4；\
    1 2 3 4 5运行次数就是2 2对5 3对4
    struct ListNode *pre = head,*fin = NULL,*pre_fin = NULL; //pre在前走，fin永远指向最后一个指针,pre_fin的前一个指针 

    while(pre != NULL) {
        run_tim += 1;
        pre = pre->next;
	}
    run_tim = (run_tim-1)/2;
    if(run_tim > 0) {
    	pre = head;
	    while(run_tim--) {
	        pre_fin = pre->next;
	        fin = pre_fin->next;
			while( fin->next != NULL) {
				pre_fin = pre_fin->next;
				fin = fin->next;  //指向最后一个节点 
			}
			fin->next = pre->next;
			pre->next = fin;
			pre_fin->next = NULL;
			pre = pre->next->next;
	    }
	}
    pre = NULL;
    pre_fin = NULL;
    fin = NULL;
}