Also, preserve the original relative order of elements in both the groups (i.e elements smaller than 'x' form one group and elements equal to or greater than 'x' form another group. The relative order should be maintained in both the groups.)

Example 1:-

a={2,6,3,5,1,7}

x=5

Output : 2 3 1 6 5 7

All the elements smaller than 5 come before 5 and the relative order of the moved elements is 
   preserved (2,3,1) & (6,5,7)

Example 2:-

a={1,4,2,5,3}

x=4

output : 1 2 3 4 5

The original question was for a singly linked list . I wrote the algorithm for an array and I wanted to know if it can be ported to the linked list variation. Also, is there a better way of doing this?

   #include <bits/stdc  .h>
using namespace std;

void swap(vector<int> &a, int i, int j)
{
    int i2 = i;
    int x = a[j];
    int temp1 = a[i];
    int temp2;
    while (i < j)
    {
        temp2 = a[i   1];
        a[i   1] = temp1;
        temp1 = temp2;
        i  ;
    }
    a[i2] = x;
}

void solve(vector<int> &a, int num)
{
    int n = a.size();
    int i = 0, j = 1;
    while (j < n)
    {
        if (a[i] < num)
            i  ;
        if (a[i] >= num && a[j] < num)
            swap(a, i, j);
        j  ;
    }
}

int main()
{
    vector<int> a = {2, 6, 3, 5, 1, 7};
    int num = 5;
    solve(a, num);
    for (auto el : a)
        cout << el << " ";
    return 0;
}

CodePudding user response：

When working with linked lists, the concept of swapping is not really useful for linked lists. Instead you would move nodes.

Here is a possible implementation:

#include <iostream>

class Node {
    public:
    int value;
    Node * next;
    
    Node(int value, Node * next) {
        this->value = value;
        this->next = next;
    }

    Node(int value) {
        this->value = value;
        this->next = nullptr;
    }

    void print() {
        Node * node = this;
        while (node != nullptr) {
            std::cout << node->value << " -> ";
            node = node->next;
        }
        std::cout << "NULL\n";
    }

    Node * partition(int pivot) {
        if (this->next == nullptr) return this; // Quick exit
        Node * preHead = new Node(0); // Dummy
        Node * preMid = new Node(0, this); // Dummy
        Node * lessTail = preHead;
        Node * prev = preMid;
        while (prev->next) {
            Node * curr = prev->next;
            if (curr->value < pivot) {
                prev->next = curr->next; // remove curr
                lessTail->next = curr; // insert curr
                lessTail = curr; 
            } else {
                prev = curr; // keep curr where it is
            }
        }
        lessTail->next = preMid->next;
        delete preMid;
        Node * head = preHead->next;
        delete preHead;
        return head;
    }
};

int main() {
    // Construct the list from example #2
    Node * head = new Node(1,
                new Node(4,
                new Node(2,
                new Node(5,
                new Node(3)))));
    head->print();  // 1 -> 4 -> 2 -> 5 -> 3 -> NULL
    head = head->partition(4);
    head->print();  // 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    // ...    
}

This code uses two temporary node instances, because that makes the code a bit easier. But it is also possible to do it without those dummy nodes. In that case you must perform some nullpointer checks to see when to assign to a next property or to a head variable.