Another approach using stack.


  • 0
    S
    class Solution {
    public:
    	ListNode* last(vector<ListNode*>& list) {
    		ListNode* h = list[list.size() - 1];
    		list.pop_back();
    		list[list.size() - 1]->next = NULL;
    		return h;
    	}
    	void reorderList(ListNode* head) {
    		vector<ListNode*> stack;
    		ListNode* p1 = NULL;
    		ListNode* p2 = NULL;
    		if (!head||!head->next ||!head->next->next)
    			return;
    		p1 = head;
    		while (p1) {
    			stack.push_back(p1);
    			p1 = p1->next;
    		}
    
    		p1 = head;
    
    		while (p1->next) {
    			p2 = last(stack);
    			p2->next = p1->next;
    			p1->next = p2;
    
    			if(p1->next)
    				p1 = p1->next;
    			if (p1->next)
    				p1 = p1->next;
    		}
    		p1 = head;
    	}
    };
    

Log in to reply
 

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