One fake head to make swapping cleaner


  • 0
    Z
    class Solution {
    public:
            ListNode* partition(ListNode* head, int x)
            {
                if ((head == NULL) || (head->next == NULL))
                {
                    return head;
                }
                ListNode fakeHead(0);
                ListNode* ins = &fakeHead;
                ins->next = head;
                if (head->val < x)
                {
                    do
                    {
                        ins = ins->next;
                    } while ((ins->next != NULL) && (ins->next->val < x));
                }
                ListNode* prev = ins;
                ListNode* ptr = ins->next;
                bool seen = false;
                while (1)
                {
                    while ((ptr != NULL) && (ptr->val >= x))
                    {
                        seen = true;
                        prev = ptr;
                        ptr = ptr->next;
                    }
                    if (ptr == NULL)
                    {
                        break;
                    }
                    if (seen)
                    {
                        ListNode* tmp = ptr->next;
                        ptr->next= ins->next;
                        ins->next = ptr;
                        prev->next = tmp;
                        ins = ptr;
                    }
                    prev = ptr;
                    ptr = ptr->next;
                }
                return fakeHead.next;
            }
    };

Log in to reply
 

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