New update is available. Click here to update.

Partition List

Posted: 14 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a Singly Linked List of integers with a head pointer. Every node of the Linked List has a value written on it.

A sample Linked List

1

Now you have been given an integer value ‘K’. Your task is to rearrange this linked list such that the following conditions hold true :

1. All nodes that have a value less than ‘K’ must come before the nodes that have a value greater than equal to ‘K’.

2. All nodes must maintain the original relative order as they have present in the original linked list after rearrangement.

Input Format:

The first line of the input contains an integer ‘T’ representing the number of test cases.

The first line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.

The second line of each test case contains a single integer ‘K’.

Output Format:

For each test case return space-separated integers denoting the values of nodes of the Linked List.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
0 <= N <= 5*10^4
1 <= DATA <= 10^9 and DATA != -1
1 <= K <= 10^9   

Time Limit: 1 sec