Solution
The problem wants us to reform the linked list structure, such that the
elements lesser that a certain value x
, come before the elements greater or
equal to x
. This essentially means in this reformed list, there would be a
point in the linked list before
which all the elements would be smaller than
x
and after
which all the elements would be greater or equal to x
.
Let's call this point as the JOINT
.
Reverse engineering the question tells us that if we break the reformed list
at the JOINT
, we will get two smaller linked lists, one with lesser elements
and the other with elements greater or equal to x
. In the solution, our main aim
is to create these two linked lists and join them.
Approach 1: Two Pointer Approach
Intuition
We can take two pointers before
and after
to keep track of the two linked
lists as described above. These two pointers could be
used two create two separate lists and then these lists could be combined to
form the desired reformed list.
Algorithm

Initialize two pointers
before
andafter
. In the implementation we have initialized these two with a dummyListNode
. This helps to reduce the number of conditional checks we would need otherwise. You can try an implementation where you don't initialize with a dummy node and see it yourself!Dummy Node Initialization

Iterate the original linked list, using the
head
pointer. 
If the node's value pointed by
head
is lesser thanx
, the node should be part of thebefore
list. So we move it tobefore
list. 
Else, the node should be part of
after
list. So we move it toafter
list. 
Once we are done with all the nodes in the original linked list, we would have two list
before
andafter
. The original list nodes are either part ofbefore
list orafter
list, depending on its value.Note:
Since we traverse the original linked list from left to right, at no point would the order of nodes change relatively in the two lists. Another important thing to note here is that we show the original linked list intact in the above diagrams. However, in the implementation, we remove the nodes from the original linked list and attach them in the before or after list. We don't utilize any additional space. We simply move the nodes from the original list around. 
Now, these two lists
before
andafter
can be combined to form the reformed list.
We did a dummy node initialization at the start to make implementation easier, you don't want that to be part of the returned list, hence just move ahead one node in both the lists while combining the two list. Since both before and after have an extra node at the front.
Complexity Analysis
 Time Complexity: , where is the number of nodes in the original linked list and we iterate the original list.
 Space Complexity: , we have not utilized any extra space, the point to note is that we are reforming the original list, by moving the original nodes, we have not used any extra space as such.
Analysis written by: @godayaldivya.