Partition

Posted: 22 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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
Try Problem