Partition Linked List

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given the head of a singly linked list and an integer X. Your task is to partition the linked list around the value X such that:

All nodes with values less than X come first.

All nodes with values equal to X come next.

All nodes with values greater than X come at the end.

Crucially, the original relative order of the nodes within each of these three partitions must be preserved.

Your function should rearrange the nodes in-place (or by creating new lists and linking them) and return the head of the newly formed partitioned list.

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

Input Format:

The first line contains the node data for the linked list, separated by single spaces. The input is terminated by -1.

The second line contains a single integer X, the partition value.

Output Format:

Print a single line containing the data of the nodes in the partitioned linked list, separated by spaces.

Note:

The most straightforward and stable approach is to create three separate temporary linked lists: one for "less than X", one for "equal to X", and one for "greater than X". Iterate through the original list once, appending each node to the appropriate temporary list. Finally, connect the three temporary lists together to form the final result.

Sample Input 1:

1 4 3 2 5 2 -1
3

Sample Output 1:

1 2 2 3 4 5

Explanation for Sample 1:

Original list: 1 -> 4 -> 3 -> 2 -> 5 -> 2
Partition value X = 3.
Nodes less than 3: 1, 2, 2 (in that order).
Nodes equal to 3: 3.
Nodes greater than 3: 4, 5 (in that order).
Concatenating these lists gives: 1 -> 2 -> 2 -> 3 -> 4 -> 5.

Sample Input 2:

10 4 20 10 3 -1
10

Sample Output 2:

4 3 10 10 20

Explanation for Sample 2:

Original list: 10 -> 4 -> 20 -> 10 -> 3
Partition value X = 10.
Nodes less than 10: 4, 3.
Nodes equal to 10: 10, 10.
Nodes greater than 10: 20.
Final list: 4 -> 3 -> 10 -> 10 -> 20.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= Number of nodes <= 1000
-1000 <= Node Value, X <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Partition Linked List

Console