Partition List

    You should preserve the original relative order of the nodes in each of the
    two partitions.

    题解

    此题出自 CTCI 题 2.4，依据题意，是要根据值x对链表进行分割操作，具体是指将所有小于x的节点放到不小于x的节点之前，咋一看和快速排序的分割有些类似，但是这个题的不同之处在于只要求将小于x的节点放到前面，而并不要求对元素进行排序。

    Python

    Java

    1. 异常处理
    2. 引入左右两个dummy节点及left和right左右尾指针
    3. 遍历原链表
    4. 处理右链表，置为空(否则如果不为尾节点则会报错，处理链表时 以 null 为判断)，将右链表的头部链接到左链表尾指针的next，返回左链表的头部

    复杂度分析

    遍历链表一次，时间复杂度近似为 O(n), 使用了两个 dummy 节点及中间变量，空间复杂度近似为 O(1).