Simplest C++ solution in O(n)


  • 0
    R
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        
        ListNode* partition(ListNode* head, int x) {
            
            if(!head || head->next==NULL)
                return head;
            
            ListNode *dummy=new ListNode(INT_MIN);
            dummy->next=head;
            head=dummy;
            
            ListNode *here=NULL, *p=head , *save=NULL, *temp=NULL; 
            
            while(p && p->val<x)
            {
                here=p;
                p=p->next;
            }
            
            while(p)
            {   
                if(p->val < x)
                {
                    temp=here->next;
                    here->next=p;
                    save->next=save->next->next;
                    p->next=temp;
                    here=here->next;
                    p=save->next;
                }
                else
                {
                    save=p;
                    p=p->next;
                }
            }
            return head->next;
        }
    };
    

Log in to reply
 

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