143_ReorderList - a920604a/leetcode GitHub Wiki

class Solution {
public:
    ListNode* reverse(ListNode *head){
        ListNode *pre = new ListNode(-1);
        pre->next = head;
        while(head->next){
            ListNode *temp = head->next;
            head->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return pre->next;
    }
    void reorderList(ListNode* head) {
        if(!head ||!head->next) return;
        int size = 0;
        for(ListNode *p = head;p;p=p->next) size++;
        ListNode *a = head, *b = head, *pre = nullptr;
        int mid = size/2;
        while(mid--){
            pre =b;
            b=b->next;
        }
        pre->next = nullptr;
        ListNode *r  = reverse(b);
        ListNode * p = a;
        a=a->next;
        while(a || r){
            if(r){
                p->next = r;
                r=r->next;
                p=p->next;
            }
            if(a){
                p->next = a;
                a=a->next;
                p=p->next;
            }
        }
        p->next = nullptr;
    }
};

class Solution {
public:
    void reorderList(ListNode* head) {
        stack<ListNode *>sta;
        ListNode *p = head;
        while(p){
            sta.push(p);
            p=p->next;
        }
        p=head;
        int size = (sta.size()-1)/2;
        while(size-- > 0 ){
            ListNode *post = p->next;
            p->next = sta.top();
            sta.pop();
            p->next->next = post;
            p=post;
            
        }
        sta.top()->next = nullptr;
        
    }
};

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next) return ;
        stack<ListNode *> sta;
        ListNode * p =head;
        while(p){
            sta.push(p);
            p=p->next;
        }
        ListNode *cur = head, *post = head->next;
        while(sta.top()!=post){
            cur->next = sta.top();
            sta.pop();
            cur=cur->next;
            
            if(sta.top()==post) break;
            cur->next = post;
            cur=cur->next;
            post=post->next;
        }
        cur->next = sta.top();
        cur->next->next= nullptr;
        
    }
};