My O(n) C++ Method with deque<ListNode*>


  • 1
    Q
       void reorderList(ListNode* head) {
    	if (head == NULL || head->next == NULL)
    		return;
    	deque<ListNode*> dq;
    	ListNode* cur = head;
    	ListNode* p = head->next;
    	while (p)
    	{
    		dq.push_back(p);
    		p = p->next;
    	}
    	while (!dq.empty())
    	{
    		cur->next = dq.back();
    		cur = cur->next;
    		dq.pop_back();
    
    		if (!dq.empty())
    		{
    			cur->next = dq.front();
    			cur = cur->next;
    			dq.pop_front();
    		}
    	}
    	cur->next = NULL;
    }

  • 0
    T

    this deque solution is very smart.


  • 0

    in-place solution is not this kind, I suppose.


Log in to reply
 

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