Partition List

Easy
0/40
Average time to solve is 15m
7 upvotes
Asked in companies
AdobeAppleSamsung

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
3 6 2 7 9 -1
6
1 3 8 7 -1
8

Sample Output 1:

3 2 6 7 9
1 3 7 8

Explanation for sample input 1:

Test case 1:
The given linked list is shown below and K = 6.

2

We can rearrange this linked as 3 -> 2 -> 6 -> 7 -> 9
Nodes having a value less than ‘K’ = [3, 2]
Nodes having a value greater than or equal to ‘K’ = [6, 7, 9]
Here [3, 2] comes before [6, 7, 9], therefore, the final list will be [3, 2, 6, 7, 9].

Test case 2:
The given linked list is shown below and K = 8.

3

We can rearrange this linked as 1 -> 3 -> 7 -> 8
Nodes having a value less than ‘K’ = [1, 3, 7]
Nodes having a value greater than or equal to ‘K’ = [8]
Here [1, 3, 7] comes before [8], therefore, the final list will be [1, 3, 7, 8].

Sample Input 2:

1
1 2 3 7 -1
5

Sample Output 2:

 1 2 3 7

Explanation for sample input 1:

Test case 1:
The given linked list is shown below and K = 5

4

We can rearrange this linked as 1 -> 2 -> 3 -> 7
Nodes having value less than ‘K’ = [1, 2, 3]
Nodes having value greater than or equal to ‘K’ = [7]
Here [1, 2, 3] comes before [7],  therefore, the final list will be [1, 2, 3, 7].
Hint

Make two-pointers and store all nodes that have values less than ‘K’ in one pointer and all nodes that have values greater or equal to ‘K’ in another pointer.

Approaches (1)
Single Traversal Approach

The idea here is to Make two-pointers and store all nodes that have values less than ‘K’ in one pointer and all nodes that have values greater or equal to ‘K’ in another pointer. Then we will merge these two to get our answer.

 

Algorithm:

  • Create two nodes that say ‘LESS’ and ‘GREATER’ to keep track of nodes that are less than ‘K’ and nodes that are greater than or equal to ‘K’
  • Create two nodes, say ‘N1’ and ‘N2’ and initialize ‘N1’ with ‘LESS’ and ‘N2’ with ‘GREATER’.
  • Run a loop until HEAD != NULL. Here ‘HEAD’ is the head of the given linked list.
  • If the value of HEAD < K then assign ‘HEAD’ in next of ‘LESS’ i.e. do LESS→NEXT = HEAD and move pointer of ‘LESS’ i.e. do LESS = LESS -> NEXT.
  • Else assign ‘HEAD’ in next of ‘GREATER’ i.e. do GREATER -> NEXT = HEAD and move the pointer of ‘GREATER’ i.e. do GREATER = GREATER -> NEXT.
  • Move pointer of ‘HEAD’ i.e. do HEAD = HEAD -> NEXT.
  • Assign NULL to next of ‘GREATER’ i.e. do GREATER -> NEXT = NULL.
  • Assign N2 -> NEXT to LESS→NEXT.
  • Return N1 -> NEXT as this is our required HEAD node.
Time Complexity

O(N), where N is the number of nodes in the Linked List.

 

In the worst case, we are doing only a single traversal of the Linked List which takes O(N) time. Hence the overall time complexity will be O(N).

Space Complexity

O(1).

 

No extra space is being used.

Code Solution
(100% EXP penalty)
Partition List
Full screen
Console