java - 在单链表中进行分区

我在练习：
编写代码，将链表围绕一个值x进行分区，使小于x的所有节点都在大于或等于x的所有节点之前。示例输入：3->5->8->5->10->2->1输出：3->1->2->10->5->5->8
我发现很难找到单一链接列表（由我自己创建，不使用库）的解决方案，我想知道我的代码中是否有不必要的代码块，是否有办法避免放入两个列表，然后合并因为它的表现似乎很慢。

    public CustomLinkedList partition(CustomLinkedList list, int x) {
    CustomLinkedList beforeL = new CustomLinkedList();
    CustomLinkedList afterL = new CustomLinkedList();
    LinkedListNode current = list.getHead();
    while (current != null) {
        if (current.getData() < x) {
            addToLinkedList(beforeL, current.getData());
        } else {
            addToLinkedList(afterL, current.getData());
        }
        // increment current
        current = current.getNext();
    }
    if (beforeL.getHead() == null)
        return afterL;
    mergeLinkedLists(beforeL, afterL);
    return beforeL;
}

public void addToLinkedList(CustomLinkedList list, int value) {
    LinkedListNode newEnd = new LinkedListNode(value);
    LinkedListNode cur = list.getHead();
    if (cur == null)
        list.setHead(newEnd);
    else {
        while (cur.getNext() != null) {
            cur = cur.getNext();
        }
        cur.setNext(newEnd);
        cur = newEnd;
    }
}

public void mergeLinkedLists(CustomLinkedList list1, CustomLinkedList list2) {
    LinkedListNode start = list1.getHead();
    LinkedListNode prev = null;
    while (start != null) {
        prev = start;
        start = start.getNext();
    }
    prev.setNext(list2.getHead());
}

custumlinkedList包含两个属性：-linkedlistnode是头，int是大小。
LinkedListNode包含两个属性：一个是指向下一个节点的LinkedListNode类型，另一个是int:data-value类型
谢谢您。

最佳答案

我认为维持两份名单不是问题使用一个列表是可能的，但代价是失去了一些简单性。
主要的问题似乎是addToLinkedList(CustomLinkedList list, int value)方法。
它遍历整个列表以添加新元素。
另一种选择是总是在列表的前面添加元素。这也会产生一个有效的解决方案，并且运行得更快。