Ugly but 1ms faster than fake heads....


  • 0
    Z

    Longer and uglier than the fake heads solution. But 1 ms faster :) A lot of work for little benefit...

    class Solution {
    public:
           ListNode* partition(ListNode* head, int x)
        {
            if ((head == NULL) || (head->next == NULL))
            {
                return head;
            }
            ListNode* ins = NULL;
            ListNode* prev1 = NULL;
            ListNode* ptr1 = head;
            
            if (ptr1->val < x)
            {
                ins = ptr1;
                while (ins->next->val < x)
                {
                    ins = ins->next;
                    if (ins->next == NULL)
                    {
                        return head;
                    }
                }
                ptr1 = ptr1->next;
            }
            
            
            bool seen = false;
            while (ptr1 != NULL)
            {
                if (ptr1->val >= x)
                {
                    seen = true;
                    prev1 = ptr1;
                    ptr1 = ptr1->next;
                }
                else
                {
                    if (ins == NULL)
                    {
                        if ((prev1 == NULL) || (!seen))
                        {
                            prev1 = ptr1;
                            ptr1 = ptr1->next;
                            if (ins == NULL)
                            {
                                ins = head;
                            }
                            else
                            {
                                ins = ins->next;
                            }
                        }
                        else
                        {
                            ListNode* tmp = head;
                            head = ptr1;
                            ListNode* tmp2 = ptr1->next;
                            ptr1->next = tmp;
                            prev1->next = tmp2;
                            ins = head;
                            prev1 = ptr1;
                            ptr1 = ptr1->next;
                        }
                    }
                    else
                    {
                        if (seen)
                        {
                            ListNode* tmp = ins->next;
                            ListNode* tmp2 = ptr1->next;
                            ins->next = ptr1;
                            ptr1->next = tmp;
                            prev1->next = tmp2;
                            ins = ptr1;
                        }
                        prev1 = ptr1;
                        ptr1 = ptr1->next;
                    }
                }
            }
            
            
            return head;
        }
    
    };

Log in to reply
 

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