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
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
after which all the elements would be greater or equal to
Let's call this point as the
Reverse engineering the question tells us that if we break the reformed list
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
We can take two pointers
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.
Initialize two pointers
after. In the implementation we have initialized these two with a dummy
ListNode. 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
If the node's value pointed by
headis lesser than
x, the node should be part of the
beforelist. So we move it to
Else, the node should be part of
afterlist. So we move it to
Once we are done with all the nodes in the original linked list, we would have two list
after. The original list nodes are either part of
afterlist, 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
aftercan 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.
- 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.