gistfile1.txt

/**
 * 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) {
        ListNode *big_head, *big_tail, *small_head, *small_tail;
        ListNode* sentry = head;
        big_head = small_head = NULL;
        ListNode* placeholder;
        while(sentry != NULL) {
            placeholder = sentry->next;
            if (sentry->val < x) {
                if (small_head == NULL) {
                    small_head = sentry;
                    small_tail = small_head;
                } else {
                    small_tail->next = sentry;
                    small_tail = small_tail->next;
                }
              //  small_tail->next = NULL;
            } else {
                if (big_head == NULL) {
                    big_head = sentry;
                    big_tail = big_head;
                } else {
                    big_tail->next = sentry;
                    big_tail = big_tail->next;
                }

            }
            
            sentry = placeholder;
        }
        if (big_tail)    
            big_tail->next = NULL;        
        if (small_tail != NULL) {
            small_tail->next = big_head;
            
            return small_head;
        } else {
            return head;
        }
    }
};