Easy to understand with O(n) time and O(1) space complexity in java


#1
public ListNode partition(ListNode A, int B) {
        ListNode curr = A;
        ListNode prev = null;
        ListNode node = null;
        while(curr != null && curr.val < B) { // Traverse till values less than B because we don't need to change the
            prev = curr;
            curr = curr.next;
        }
        if(curr == null) { // If all values are less return the list 
            return A;
        }

        while(curr != null) {
            if(curr.next != null && curr.next.val < B) {
                node = curr.next;
                curr.next = curr.next.next;

                if(prev == null) {// We need to insert at head because it is the first minimum
                    node.next = A;
                    prev = node;
                    A = prev; // New head
                } else { // There are some items alredy present in the left side of linked list less than B
                    ListNode temp = prev.next;
                    prev.next = node;
                    node.next = temp;
                    prev = prev.next;
                }
            } else {
                curr = curr.next;
            }
        }
        return A;
    }