题解 | #重排链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        //现在是用一个列表存下来了所有的值，
        if(head == NULL) return; //空链表特判
        int len=0;
        auto x = head;
		while(x) {len++;x=x->next;} //统计链表长度
        //通过头插法，将后半部分链表进行反转
        auto mid = new ListNode(-1);
        x = head;
        for(int i=0;i<len;i++){ //利用头插法将链表后半部进行反转
            if(i>=(len >> 1)){
                auto tmp = x->next;
                x->next = mid->next;
                mid->next = x;
                x = tmp;
            }else x = x->next;
        }
	  //此时前半部分正向，后半部分反向，正常进行插入即可
        mid = mid->next;
        x = head;
        for(int i=0;i<(len>>1);i++){
            auto tmp = mid->next;
            mid->next = x->next;
            x->next = mid;
            x = mid->next;
            mid=tmp;
        }
        x->next =  NULL;
    }
};