Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

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

Solution in C++

/*
* File     : partition-list.cpp
*/

#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;

}