Last Updated: 22 Feb, 2021
Partition
Easy
Asked in companies
You are given a linked list and a number ‘x’, You have to partition the linked list in such a way that all nodes with a value less than 'x' comes before the nodes with values greater than or equal to 'x'. The original relative order should be preserved.
Input Format
The first line of input contains an integer 'T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first line of each test case contains integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.
The second line contains an integer ‘x’.
Output Format
For each test case, print space-separated integers terminated by -1 denote the elements of the given linked lists which are sorted in non-decreasing order.
The output of each test case should be printed in a new line.
Constraints
1 <= ’T’ <= 50
-1000 <= ’x’ <= 1000
0 <= Length of linked list <= 10000
-1000 <= "data" <= 1000
"data" != -1, 'x' != -1
Where 'T' is the number of test cases. 'x' denotes the given integer and "data" denotes the linked list node value.
Approaches
Explanation:-
The key idea will be to create two vectors ‘small’ and ‘big’ and store all the values less than ‘x’ in the small vector and values greater than ‘x’ in the big vector. In this way, the relative order will be preserved.
The algorithm is as follows:
- Create two vectors ‘small’ and ‘big’
- Iterate the linked list. If the value of a current node is less than ‘x’ insert the value of a current node in a small vector else insert the value of a current node in a big vector.
- Insert all the values of ‘big’ vector at the end of ‘small’ vector.
- After inserting update the value of ith node of a given linked list with the ith value of ‘small’ vector.
- Return the head of the given linked list
Explanation- The key idea is to traverse the linked list and split it into two parts such that the value of nodes less than ‘x’ is in the first part and the value of nodes greater than equal to ‘x’ is in the second part.
The algorithm is as follow:-
- Make two linked list initially initialized with NULL.
- Iterate over the linked list. If the value of a current node is less than ‘x’ then insert this node at the end of the first linked list else insert it at the end of the second linked list.
- After iterating over the linked list connect the second linked list to the end of the first linked list.
- We do this by making the last element ->next of the list equal to the head of the second linked list.
- Return the head of the first linked list.