C++ 6ms, simple solution


  • 0
    J
    /*
    The main idea is to find the node that hass less value than x, and move the small node before the large nodes. 
    use two pointers to indicate the begin of large group and the end of large group; 
    for example in a list 
    1->4->3->2->5->2 and x = 3
    pt1 will point to 1, i.e. right before the large group (i.e., 4->3)
    pt2 will point to 3
    */
    class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            ListNode dummy(x-1); // use a smalller value to ensure this dummy node is in the small group
            ListNode *pt=head, *pt1 = &dummy, *pt2=0;
            dummy.next=head;
            
            while(pt){
                if(pt->val < x){
                    //move the new small node point if pt2 has been assigned (ie. larger node has been found)
                    if (pt2){
                        pt2->next=pt->next;
                        pt->next=pt1->next;
                        pt1->next=pt;
                    }
                    //reasign pt1, the nearest smaller one before the big group
                    pt1=pt;
                    pt= (pt2) ? pt2->next : pt->next;
                }
                else {
                    pt2=pt;
                    pt=pt->next;
                }
            }
            return dummy.next;
        }
    };
    
    

Log in to reply
 

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