Partition List

PROBLEM :

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/**
 * 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==NULL||head->next==NULL)
            return head ;
           
        ListNode* start,*end,*temp,*ptr ;
        start=NULL,end=NULL ;
       
        while(head!=NULL&&head->val>=x){
            if(start==NULL){
                start=head ;
                end=head ;
                head=head->next ;
                end->next=NULL ;
            }
            else{
                end->next=head ;
                head=head->next ;
                end=end->next ;
                end->next=NULL ;
            }
        }
       
        ptr=head ;
        if(ptr==NULL)
            return start ;
           
        while(ptr->next!=NULL){
            if(ptr->next->val>=x){
                temp=ptr->next ;
                ptr->next=temp->next ;
               
                if(start==NULL){
                    start=temp ;
                    end=temp ;
                    end->next=NULL ;
                }
                else{
                    end->next=temp ;
                    end=end->next ;
                    end->next=NULL ;
                }
            }
            else
                ptr=ptr->next ;
        }
        cout<<head->val ;
        ptr=head ;
        while(ptr->next!=NULL)
            ptr=ptr->next ;
           
        ptr->next=start ;
        return head ;
    }
};

---------------------------------------------------------------------------------