题解 | #重排链表#

 * 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 ;
        ListNode* node = new ListNode(-1);
        node->next = head;
        ListNode* node2 = node;
        while(node2->next){
            node = node->next;
            node2 = node2->next;
            if(node2->next){
                node2 = node2->next;
            }
        }
        
        ListNode* pre = new ListNode(-1);
        ListNode* tar = node->next;
        node->next = NULL;
        // tou cha 
        while(tar){
            ListNode* next =tar->next;
            tar->next = pre->next;
            pre->next = tar;
            tar = next;
        }
        ListNode* dummary = head;
        // 按次插入
        //1 2 3 4 5
        // 1 3 5 / 4 2
        // 1 4 3 2 5
        while(dummary && pre->next){
            ListNode* tmp = pre->next;
            pre->next = tmp->next;
            tmp->next = dummary->next;
            dummary->next = tmp;
            dummary = tmp->next;
        }
        return ;
        
        
       
    }
};