一、复杂一点的方法：

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
    ListNode * partition(ListNode * head, int x) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }
        ListNode *bigHead = NULL;
        ListNode *bigEnd = NULL;
        ListNode *smallHead = NULL;
        ListNode *smallEnd = NULL;
        ListNode *pPrev = head;
        ListNode *pNext = head->next;
        bool firstBig = true;
        bool firstSmall = true;

        while (pNext != NULL) {
            if (pPrev->next == pNext) {
                pPrev->next = NULL;
            }
            if (pNext->val < x) {
                if (firstSmall) {
                    smallHead = smallEnd = pNext;
                    firstSmall = false;
                } else {
                    smallEnd->next = pNext;
                    smallEnd = smallEnd->next;
                }
            } else {
                if (firstBig) {
                    bigHead = bigEnd = pNext;
                    firstBig = false;
                } else {
                    bigEnd->next = pNext;
                    bigEnd = bigEnd->next;
                }
            }
            pPrev = pNext;
            pNext = pNext->next;
        }
        
        if (head->val < x) {
            head->next = smallHead;
            smallHead = head;
        } else {
            head->next = bigHead;
            bigHead = head;
        }
        
        if (bigHead == NULL) {
            return smallHead;
        }
        
        if (smallHead == NULL) {
            return bigHead;
        }
        
        smallEnd->next = bigHead;
        bigEnd->next = NULL;
        return smallHead;
    }
};

虽然也能实现，但是代码写起来比较费劲，

二、摘除法

首先创建两个空节点，然后将满足条件的节点分别挂到这两个界节点的下面，最后再将这两个链表合并，实现起来简单易懂，俗称摘除法

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
    ListNode * partition(ListNode * head, int x) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }
        ListNode *smallHead = new ListNode(-1);
        ListNode *bigHead = new ListNode(-1);
        ListNode *smallEnd = smallHead;
        ListNode *bigEnd = bigHead;
        while (head != NULL) {
            if (head->val < x) {
                smallEnd->next = head;
                smallEnd = head;
            } else {
                bigEnd->next = head;
                bigEnd = head;
            }
            head = head->next;
        }
        
        smallEnd->next = bigHead->next;
        bigEnd->next = NULL;
        return smallHead->next;
    }
};

这种方法可以用到很多与链表相关的题目中，比如下面这道题

翻转链表 II
描述
翻转链表中第m个节点到第n个节点的部分
m，n满足1 ≤ m ≤ n ≤ 链表长度
您在真实的面试中是否遇到过这个题？是
题目纠错
样例
给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null
挑战
在原地一次翻转完成
题目链接：https://www.lintcode.com/problem/reverse-linked-list-ii/description
实现如下：

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: ListNode head is the head of the linked list 
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    ListNode * reverseBetween(ListNode * head, int m, int n) {
        // write your code here
        ListNode *firstHead = new ListNode(-1);
        ListNode *firstEnd = firstHead;
        ListNode *secondHead = new ListNode(-1);
        ListNode *secondEnd = secondHead;
        
        int i = 1;
        while (head != NULL) {
            if (i < m) {
                firstEnd->next = head;
                firstEnd = head;
            } else if (i >= m && i <= n) {      
                secondEnd->next = head;
                secondEnd = head;
            } else {
                break;
            }
            head = head->next;
            ++i;
        }
        
        secondEnd->next = NULL;     
        ListNode *pNext = secondHead->next;
        secondEnd = pNext;
        if (pNext->next != NULL) {
            ListNode *pPrev = pNext;
            pNext = pNext->next;
            while (pNext != NULL) {
                ListNode *temp = pNext->next;
                pNext->next = pPrev;
                pPrev = pNext;
                pNext = temp;
            }
            secondHead->next = pPrev;
        }
        
        firstEnd->next = secondHead->next;
        secondEnd->next = head;
        
        return firstHead->next;
    }
};

引：
https://blog.csdn.net/guoziqing506/article/details/51291959