对链表进行分区

我正在尝试基于链表数据结构来解决这个算法问题。问题如下：

给定一个链表和一个值 x，对其进行分区，使得所有小于 x 的节点都位于大于或等于 x 的节点之前。 您应该保留两个分区中节点的原始相对顺序。

例如，

给定 1->4->3->2->5->2 且 x = 3， 返回 1->2->2->4->3->5。

我的问题解决方案是：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return null;
        ListNode headNode = new ListNode(-1);
        headNode.next = head;

        ListNode tail = head;
        while(tail.next!=null){
            tail = tail.next;
        }
        ListNode actualTail = tail;
        ListNode current = headNode;
        while(current!=actualTail && current.next!=actualTail){
            if(current.next.val >= x && current.next!=tail){
                System.out.println("Moving "+current.next.val+" to end of list, ahead of "+tail.val);
                ListNode temp = current.next;
                current.next = current.next.next;
                tail.next = temp;
                tail = tail.next;
                tail.next = null;
            }else{
                current = current.next;    
            }

        }
        return headNode.next;
    }
}

虽然某些测试用例可以很好地使用此代码（例如上面提到的代码），但有一组测试用例失败，因为我无法维护列表中节点的原始相对顺序。

例如： 列表 = [1->2] x = 0

我的结果： [2,1]

预期的： [1,2]

任何帮助将不胜感激。

我认为你可以用更简单的方式做到这一点：

• 保留 2 个列表，一个用于较低节点，另一个用于较大节点。
• 迭代列表，将节点添加到相应的列表中。
• 将较低的列表与较大的列表连接起来

像这样的事情：

public ListNode Partition(ListNode head, int x)
{
    ListNode lowerHead = null, lowerTail = null;              //Head and Tail of lower list
    ListNode greaterHead = null, greaterTail = null;          //Head and Tail of greater list

    ListNode current = head;

    while (current != null)
    {
        if (current.val < x)
        {
            if (lowerHead == null) lowerHead = current;      //If is the first node in the list
            if (lowerTail == null) lowerTail = current;      //set the head an tail to the same value
            else lowerTail = lowerTail.next = current;       //Otherwise, add the node and update the tail
        }
        else
        {
            if (greaterHead == null) greaterHead = current;  //If is the first node in the list
            if (greaterTail == null) greaterTail = current;  //set the head an tail to the same value
            else greaterTail = greaterTail.next = current;   //Otherwise, add the node and update the tail
        }

        current = current.next;
    }

    if (greaterHead != null)
        greaterTail.next = null;

    if (lowerHead == null) return greaterHead;
    else
    {
        lowerTail.next = greaterHead;
        return lowerHead;
    }
} 

由于节点是按照原始列表中的显示方式添加的，所以顺序得以保留