分隔链表 ！

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/partition-list-lcci
class Solution {
    public ListNode partition(ListNode head, int x) {

        
        // 构建两个新链表
        // 大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

        // 设置一个指针，执行大链表的头结点
        ListNode bigHead = new ListNode(-1);
       
        // 设置一个指针，执行大链表的尾结点
        ListNode bigTail = bigHead;

        // 设置一个指针，执行小链表的头结点
        ListNode smallHead = new ListNode(-1);

        // 设置一个指针，执行小链表的尾结点
        ListNode smallTail = smallHead;
     
        // 开始遍历原链表 head，直到遍历到尾部位置
        // 在遍历的过程查看当前节点的值
        while ( head != null) {
            
            // 如果当前节点的值小于了特定值 x
            if (head.val < x) {
                // 那么我们就把这个节点添加到小链表中
                // 操作就是让小链表中的尾节点的 next 指针指向这个节点
                smallTail.next = head;

                // 同时，小链表中的尾节点位置发生了变化，也移动到 head 这个位置
                smallTail = head;
            } else {
                 // 否则，如果当前节点的值大于或者等于了特定值 x
                 // 那么我们就把这个节点添加到大链表中
                 // 操作就是让大链表中的尾节点的 next 指针指向这个节点                 
                 bigTail.next = head;

                 // 同时，大链表中的尾节点位置发生了变化，也移动到 head 这个位置
                 bigTail = head;
            }

            // 操作完当前节点的值之后，继续去查看链表中的下一个节点
            head = head.next;
        }
         
        // 通过上面的循环，原链表已经被分割为两个部分
        // 其中，大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）
        // 接下来，我们把大小链表串联起来

        // 让小链表的尾节点的 next 指针指向大链表虚拟头节点的下一个节点
        smallTail.next = bigHead.next;

        // 让大链表的尾节点的 next 指针指向 null
        bigTail.next = null;

        // 最后返回小链表的虚拟头节点的下一个节点就行
        return smallHead.next;
    }

}

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/partition-list-lcci
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
                
        // 构建两个新链表
        // 大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

        // 设置一个指针，执行大链表的头结点
        ListNode *bigHead = new ListNode(-1);
       
        // 设置一个指针，执行大链表的尾结点
        ListNode *bigTail = bigHead;

        // 设置一个指针，执行小链表的头结点
        ListNode *smallHead = new ListNode(-1);

        // 设置一个指针，执行小链表的尾结点
        ListNode *smallTail = smallHead;
     
        // 开始遍历原链表 head，直到遍历到尾部位置
        // 在遍历的过程查看当前节点的值
        while ( head != NULL) {
            
            // 如果当前节点的值小于了特定值 x
            if (head->val < x) {
                // 那么我们就把这个节点添加到小链表中
                // 操作就是让小链表中的尾节点的 next 指针指向这个节点
                smallTail->next = head;

                // 同时，小链表中的尾节点位置发生了变化，也移动到 head 这个位置
                smallTail = head;
            } else {
                 // 否则，如果当前节点的值大于或者等于了特定值 x
                 // 那么我们就把这个节点添加到大链表中
                 // 操作就是让大链表中的尾节点的 next 指针指向这个节点                 
                 bigTail->next = head;

                 // 同时，大链表中的尾节点位置发生了变化，也移动到 head 这个位置
                 bigTail = head;
            }

            // 操作完当前节点的值之后，继续去查看链表中的下一个节点
            head = head->next;
        }
         
        // 通过上面的循环，原链表已经被分割为两个部分
        // 其中，大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）
        // 接下来，我们把大小链表串联起来

        // 让小链表的尾节点的 next 指针指向大链表虚拟头节点的下一个节点
        smallTail->next = bigHead->next;

        // 让大链表的尾节点的 next 指针指向 null
        bigTail->next = NULL;

        // 最后返回小链表的虚拟头节点的下一个节点就行
        return smallHead->next;
    }
};

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# https://leetcode-cn.com/problems/partition-list-lcci
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        # 构建两个新链表
        # 大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        # 小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

        # 设置一个指针，执行大链表的头结点
        bigHead =  ListNode(-1)
       
        # 设置一个指针，执行大链表的尾结点
        bigTail = bigHead

        # 设置一个指针，执行小链表的头结点
        smallHead =  ListNode(-1)

        # 设置一个指针，执行小链表的尾结点
        smallTail = smallHead
     
        # 开始遍历原链表 head，直到遍历到尾部位置
        # 在遍历的过程查看当前节点的值
        while head != None :
            
            # 如果当前节点的值小于了特定值 x
            if head.val < x :
                # 那么我们就把这个节点添加到小链表中
                # 操作就是让小链表中的尾节点的 next 指针指向这个节点
                smallTail.next = head

                # 同时，小链表中的尾节点位置发生了变化，也移动到 head 这个位置
                smallTail = head
            else :
                 # 否则，如果当前节点的值大于或者等于了特定值 x
                 # 那么我们就把这个节点添加到大链表中
                 # 操作就是让大链表中的尾节点的 next 指针指向这个节点                 
                 bigTail.next = head

                 # 同时，大链表中的尾节点位置发生了变化，也移动到 head 这个位置
                 bigTail = head
            

            # 操作完当前节点的值之后，继续去查看链表中的下一个节点
            head = head.next
        
         
        # 通过上面的循环，原链表已经被分割为两个部分
        # 其中，大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        # 小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）
        # 接下来，我们把大小链表串联起来

        # 让小链表的尾节点的 next 指针指向大链表虚拟头节点的下一个节点
        smallTail.next = bigHead.next

        # 让大链表的尾节点的 next 指针指向 None
        bigTail.next = None

        # 最后返回小链表的虚拟头节点的下一个节点就行
        return smallHead.next