Descrition

Submission

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == NULL) return head;
        ListNode *left = NULL, *leftEnd = NULL, *right = NULL, *rightEnd = NULL, *next = NULL;

        for(ListNode* ptr = head; ptr != NULL; ptr = next) {
            next = ptr->next;
            if(ptr->val < x) {
                if(left == NULL) {
                    left = leftEnd = ptr;
                    left->next = NULL;
                } else {
                    leftEnd->next = ptr;
                    leftEnd = leftEnd->next;
                    leftEnd->next = NULL;
                }
            } else {
                if(right == NULL) {
                    right = rightEnd = ptr;
                    right->next = NULL;
                } else {
                    rightEnd->next = ptr;
                    rightEnd = rightEnd->next;
                    rightEnd->next = NULL;
                }
            }
        }

        ListNode* res = NULL, *resEnd = NULL;

        if(res == NULL) {
            res = left;
            resEnd = leftEnd;
        }

        if(res == NULL) {
            res = right;
            resEnd = rightEnd;
        } else {
            resEnd->next = right;
            if(resEnd) {
                resEnd = rightEnd;
            }
        }

        return res;
    }
};