题解 | #重排链表#

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //法一：空间复杂度O（n）
    /*void reorderList(ListNode *head) {
        //当链表为空，只有一个结点，两个结点时，返回head即可
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr){
            return;
        }
        //可用vector存储结点
        vector<ListNode*> vec;
        while(head){
            vec.emplace_back(head);
            head=head->next;
        }
        int i=0,j=vec.size()-1;
        while(i<j){
            vec[i++]->next=vec[j];
            if(i==j){
                break;
            }
            vec[j--]->next=vec[i];
        }
        //退出来时，i=j
        vec[i]->next=nullptr;
    }
    */
    //法二
    ListNode* reverseList(ListNode *head){
        ListNode *newhead=nullptr;
        ListNode *s;
        while(head){
            s=head->next;
            head->next=newhead;
            newhead=head;
            head=s;
        }
        return newhead;
    }
    void reorderList(ListNode *head) {
        if(!head||!head->next||!head->next->next){
            return;
        }
        ListNode *slow=head,*fast=head;
        while(fast->next!=nullptr&&fast->next->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode *l1=head;
        ListNode *l2=reverseList(slow->next);
        slow->next=nullptr;
        while(l2){
            ListNode *temp1=l1->next;
            ListNode *temp2=l2->next;
            l1->next=l2;
            l2->next=temp1;
            l2=temp2;
            l1=temp1;
        }
    }
};