Leetcode 86. Partition List
head of a linked list and a value
x, partition it such that all nodes less than
x come before nodes greater than or equal to
You should preserve the original relative order of the nodes in each of the two partitions.
Input: head = [1,4,3,2,5,2], x = 3
Input: head = [2,1], x = 2
- The number of nodes in the list is in the range
-100 <= Node.val <= 100
-200 <= x <= 200
The problem says us that we need to reorder the given linked list in such a way that all the nodes which is less than a particular node, say key node must be present before all the nodes that are greater than or equal to the key node.
Note : We need to preserve the ordering, for example consider example
head = [1,4,3,2,5,2], x = 3.
Here our result will be 1,2,2,4,3,5. Not something like 1,2,2,3,4,5. We don’t want to change the ordering. 4 then 3 then 5 is the expected output.
So we need to know which are the nodes that are lesser than the key node and also the node which are greater than the key node. For this we can make use of two dummy nodes and just traverse through the given input list. Store the elements to the respective dummy nodes.
Finally from the last point of the dummy node which is tracking the less than key nodes, point the next to the greater tracking nodes head.
- Initialise two dummy nodes say lesser, greater. Also initialise 3 pointers that will go through the input head node, lesser node and greater node.
- Traverse through the given list.
- Check whether the current node is less than the key, if yes store inside the lesser node and move the pointer.
- Otherwise store inside the greater node and move the pointer.
- Finally adjust the pointers accordingly to properly frame the final list.
Time and Space Complexity
We are just traversing through the list once. Suppose length of the linked list is n, then time complexity will be O(n).
We are not making use of any extra space rather than the dummy nodes which gets garbage collected. So O(1) is the space complexity.
Note : Please correct me if I made error regarding the space complexity. Thank you.