86. Partition List

O(n) time O(1) space

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode smaller, larger, *s = &smaller, *l = &larger;
        for (auto p = head; p; p = p->next) {
            if (p->val < x) {
                s->next = p;
                s = s->next;
            } else {
                l->next = p;
                l = l->next;
            }
        }
        s->next = larger.next;
        l->next = nullptr;
        return smaller.next;
    }
};