本文共 1967 字，大约阅读时间需要 6 分钟。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {
   public:    void reorderList(ListNode* head) {
           ListNode* cur = head;        queue
   
     q_data;        stack
    
      s_data;        int num = 0;        while(cur!=nullptr){
               q_data.push(cur);            s_data.push(cur);            cur=cur->next;            num++;        }        ListNode* out = new ListNode(0);        cur = out;        for(int i=0; i<(num+1)/2; i++) {
               ListNode* x = q_data.front();            q_data.pop();            ListNode* y = s_data.top();            s_data.pop();            if(x!=y){
                   cur->next = x;                x->next =y;                y->next = nullptr;                cur = y;            }else{
                   cur->next = x;                x->next = nullptr;            }        }        head = out->next;    }};
    
   

解法二：先找中点，翻转后半段再合并

class Solution {
   public:    void reorderList(ListNode* head){
           if(!head){
   return ;}        ListNode* slow=head;        ListNode* fast=head;        while(fast && fast->next){
               slow = slow->next;            fast = fast->next->next;        }        ListNode* preNode = nullptr;        ListNode* p = slow->next;        slow->next = nullptr;        while(p){
               ListNode* next = p->next;            p->next = preNode;            preNode = p;            p = next;        }        ListNode* res = new ListNode(-1);        while(preNode){
               res->next = head;            head = head->next;            res = res->next;            res->next = preNode;            preNode = preNode->next;            res = res->next;        }        res->next = head;        head = res;    }};

转载地址：http://fvyci.baihongyu.com/