Method partition

86. Partition List/Solution.cpp:17–41

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == NULL) return head;
        ListNode * header = new ListNode(0);
        header->next = head;
        auto p1 = header, p2 = header;  // p1, p2 not NULL
        // p1 -> the last number < x, p2 -> cur
        while (p2 != NULL and p2->next != NULL) {    // see the next node value
            if (p2->next->val < x) {
                if ( p1 == p2 ) {
                    p1 = p1->next;
                    p2 = p2->next;
                    continue;
                }
                // swap 
                auto p3 = p2->next, p4 = p3->next;
                auto p1n = p1->next;
                p1->next = p3;
                p3->next = p1n;
                p2->next = p4;
                p1 = p1->next;
            } else 
                p2 = p2->next;
        }
        return header->next;
    }
};

int main() {