8ms solution with O(1) space


  • 0
    Z
    class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            ListNode* first = new ListNode(0);
            ListNode* second = new ListNode(0);
            ListNode* p = first;
            ListNode* q = second;
            ListNode* l = head;
            while(l!=NULL)
            {
                if(l->val>=x)
                {
                    q->next = l;
                    l = l->next;
                    q = q->next;
                    q->next = NULL;
                }
                else
                {
                    p->next = l;
                    l = l->next;
                    p = p->next;
                    p->next = NULL;
                }
            }
            
            p->next = second->next;
            ListNode* result = first->next;
            delete first;
            delete second;
            return result;
        }
    };

Log in to reply
 

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