Example: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5
Solution:
Let us understand the question first. The question has 2 parts:
Part 1:
Here we need to partition the list in such a way that the nodes less than “x” should come to left and greater than “x” should move to the right.
Part 2:
It also asks to preserve the original relative order of the nodes. It means we need to keep all the nodes less than “x” before the nodes having the value greater or equal to “x”.
Let us take an example:
Example 1: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->3->4->5 [wrong] Output: 1->2->2->4->3->5 [right] Example 2: Input: head = 1->2->6->3->2->1, x = 3 Output: 1->1->2->2->3->6 [wrong] Output: 1->2->2->1->6->3 [right]
Solution Explanation:
Since we have understood the basics of the question in the above section, the implementation is very simple.
In this solution, we create 2 additional linked list. “smaller” and “larger” are 2 additional lists. The “smaller” will have the values lesser than “x” and “larger” will have the values greater than “x”. Thus we shall be maintaining the relative order of the values.
Then we connect “smaller” list with “larger” list. Then assign the end of the “larger” list to null.
The above solution is done in one pass.
Test case: 1 -> 4 -> 3 -> 2 -> 5 -> 2 Pass 1: H 1 -> 4 -> 3 -> 2 -> 5 -> 2 “smaller” 1 -> “larger” NULL Pass 2: H 1 -> 4 -> 3 -> 2 -> 5 -> 2 “smaller” 1 -> “larger” 4 -> Pass 3: H 1 -> 4 -> 3 -> 2 -> 5 -> 2 “smaller” 1 -> “larger” 4 -> 3 -> Pass 3: H 1 -> 4 -> 3 -> 2 -> 5 -> 2 “smaller” 1 -> 2 -> “larger” 4 -> 3 -> Pass 4: H 1 -> 4 -> 3 -> 2 -> 5 -> 2 “smaller” 1 -> 2 -> “larger” 4 -> 3 -> 5 -> Pass 5: H 1 -> 4 -> 3 -> 2 -> 5 -> 2 “smaller” 1 -> 2 -> 2 -> “larger” 4 -> 3 -> 5 -> Finally: 1 -> 2 -> 2 -> 4 -> 3 -> 5
Solution in C++
#include<iostream> #include<vector> using namespace std; struct Node { int data; struct Node* next; }; void insert_at_begenning ( struct Node **head_pointer, int data) { // allocate memory for new node struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node)); // assign the data to new node temp_node->data = data; // initialize the new node to point to NULL temp_node->next = NULL; // if this is the first pointer, then this is the head pointer if (*head_pointer == NULL) { *head_pointer = temp_node; } else { // point the next of the present pointer to the head pointer temp_node->next = *head_pointer; //then move the reference of head pointer to the current pointer *head_pointer = temp_node; } } Node *partition_list(Node *head, int x) { Node node1; Node node2; Node *p1 = &node1, *p2 = &node2; while (head) { if (head->data < x) p1 = p1->next = head; else p2 = p2->next = head; head = head->next; } p2->next = NULL; p1->next = node2.next; return node1.next; } void display_list(struct Node **head_pointer) { // take a reference to head pointer for navigation struct Node *temp = *head_pointer; while(temp != NULL) { if(temp->next != NULL) printf("%d -> ", temp->data); else printf("%d", temp->data); //navigate to next pointer temp = temp->next; } printf("\n"); } int main() { struct Node *list= NULL; struct Node *result= NULL; insert_at_begenning(&list,2); insert_at_begenning(&list,5); insert_at_begenning(&list,2); insert_at_begenning(&list,3); insert_at_begenning(&list,4); insert_at_begenning(&list,1); int x = 3; cout<<" Input List is\n"; display_list(&list); result = partition_list(list, x); cout<<"\n Output List is\n"; display_list(&result); cout<<endl; return 0; }
Output:
Input List is 1 -> 4 -> 3 -> 2 -> 5 -> 2 Output List is 1 -> 2 -> 2 -> 4 -> 3 -> 5