题解 | #重排链表#

void reorderList(struct ListNode* head ) {  
    if(head == NULL || head->next == NULL)
        return;   //空链表或只有一个结点不用改变
    struct ListNode* fast = head; 
    struct ListNode* slow = head;
    struct ListNode *p, *r, *s;   //临时指针
    while(fast->next != NULL && fast->next->next != NULL){   //
         fast = fast->next->next;   //快指针每次走两步
         slow = slow->next;   //慢指针每次走一步
    }
     //结点个数为奇数时，fast停在最后一个结点，slow停在正中间结点，即前半段末尾
     //结点个数为偶数时，fast停在倒数第二个结点，slow停在前半段最后一个结点处
     //无论奇数还是偶数，后半段链表的第一个结点就是slow的下一个结点
    p = slow->next;   //后半段起点
    slow->next = NULL;   //前半段最后一个结点尾指针域置空
    struct ListNode* L = NULL;   //后半段链表头指针
    while(p!=NULL){   //头插法四步曲
        r = p->next;
        p->next = L;
        L = p;
        p = r;
    }
    //反转完之后，头指针L指向第一个结点，即原链表的最后一个结点
    s = head;   //s指向前半段的第一个结点
    //开始逐个插入
    while(L != NULL){
        r = L->next;
        L->next = s->next;
        s->next = L;
        s = L->next;
        L = r;
    }
}