My C++ solution with Split and Stack


  • 0
    Y
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        public:
        void reorderList(ListNode *head) {
        stack<ListNode*> s;
        ListNode *p = head,*q=head,*r;
        bool ogg=false;
        if(!(p&&p->next))
            return ;
        while (p&&q)
        {
        	s.push(p);
     	if(q->next==NULL)
    	{
    	    ogg=true;
    	    break;
    	}
    	p = p->next;
    	q = q->next->next;
        }
        head = NULL;
        if(ogg)
        {
            r=p->next;
            p->next=head;
            head=p;
            p=r;
            s.pop();
        }
        while (p && (!s.empty()))
        {
        	q = s.top();
    	s.pop();
    	q->next = p;
    	r = p->next;
    	p->next = head;
    	head = q;
    	p = r;
        }
        }
        };

Log in to reply
 

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