LeetCode Partition List

LeetCode Partition List

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode * insert(int x){

        ListNode * temp=(ListNode *)malloc(sizeof(ListNode ));

        temp->val=x;

        temp->next=NULL;

        return temp;

    }

    ListNode * partition(ListNode* head, int x) {

        if(head==NULL || head->next==NULL)

          return head;

        vector < int > v;

        ListNode * current=head;

        ListNode * prev=NULL;

        ListNode * temp;

        while(current!=NULL){

                if(current->val < x)

                {

                 temp=current;

                 v.push_back(current->val);

                 if(prev==NULL)

                   head=current->next;

                 else

                   prev->next=current->next;

                 current=current->next;

                 free(temp);

                }

                else

                {

                    prev=current;

                    current=current->next;

                }

            }

        if(v.size()==0)

          return head;

        prev=NULL;

        current=head;

        int k=0;

        while(k < v.size()){

            temp=insert(v[k]);

            if(prev==NULL){

              temp->next=head;

              head=temp;

              prev=head;

            }

            else{

            prev->next=temp;

            temp->next=current;

            prev=temp;}

            k++;

         }

      return head;

    }

};