编写一个算法，以给定值x为基准将单链表分割为两部分，所有小于x的结点排在大于或等于x的结点之前

1. 定义两个指针small和large，分别指向两个新建的空链表的头节点。
2. 遍历原链表，如果当前节点的值小于x，则将该节点插入到small链表的尾部；否则将该节点插入到large链表的尾部。
3. 将small链表的尾部指向large链表的头节点，组成新的链表。
4. 返回新的链表的头节点。

时间复杂度：O(n)，空间复杂度：O(1)。

Java实现如下：

public ListNode partition(ListNode head, int x) {
    ListNode small = new ListNode(0);
    ListNode large = new ListNode(0);
    ListNode smallTail = small, largeTail = large;
    while (head != null) {
        if (head.val < x) {
            smallTail.next = head;
            smallTail = smallTail.next;
        } else {
            largeTail.next = head;
            largeTail = largeTail.next;
        }
        head = head.next;
    }
    smallTail.next = large.next;
    largeTail.next = null;
    return small.next;
}