Using a stack iterative 68ms C++ solution.


  • 0
    S
    class Solution {
    public:
    	void reorderList(ListNode* head) {
    		vector<ListNode*> stack;
    		ListNode* mid = NULL;
    		ListNode* cur = NULL;
    		
    		if (!head||!head->next||!head->next->next)
    			return;
    			
    		cur = head;
    		mid = head;
    
    		while (cur->next) {
    			if(cur->next)
    				cur = cur->next;
    			if (cur->next)
    				cur = cur->next;
    			else
    				break;
    
    			mid = mid->next;
    		}
    
    		while (mid->next) {
    			stack.push_back(mid->next);
    			mid = mid->next;
    		}
    
    		cur = head;
    		while (stack.size()) {
    			stack[stack.size() - 1]->next = cur->next;
    			cur->next = stack[stack.size()-1];
    			cur=cur->next;
    			if (cur->next)
    				cur = cur->next;
    			stack.pop_back();
    		}
    
    		cur->next = NULL;
    	}
    };
    

Log in to reply
 

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