My C++ solution without reverse


  • 0
    L

    I am using stack to get both ends of the list, no speed or space improvement, but go through less pain to do reverse and merge

    void reorderList(ListNode* head) {
    if(!head || !head->next){
    return;
    }
    stack<ListNode*>sta;
    ListNode* item = head;
    while(item){
    sta.push(item);
    item = item->next;
    }
    item = head;
    int length = sta.size();
    while(true){
    if(length%2==1){
    if(item == sta.top()){
    sta.pop();
    item->next = NULL;
    break;
    }
    }
    else{
    if(length/2+1 == sta.size()){
    ListNode item = sta.top();
    item->next = NULL;
    break;
    }
    }
    ListNode * backitem = sta.top();
    sta.pop();
    ListNode
    nextone = item->next;
    item->next = backitem;
    backitem->next = nextone;
    item = nextone;
    }

        return;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.