Given an array 'a' and an integer 'x', arrange the elements of the (in place) such that all the elements ='x'

Question

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

you can create a vector from a linked list and vice versa, hence if you can sort one you can also sort the other. — 463035818_is_not_an_ai, Sep 27 '21 at 08:09
Yeah, but that would be cheating as per the question. You were given the head of the linked list and the question wanted you to do everything in place. — infernus-85, Sep 27 '21 at 08:10
using a solution that works is cheating but asking others for the solution is not. Hmmm... — 463035818_is_not_an_ai, Sep 27 '21 at 08:11
The test is over now. I was just trying to solve the questions that I couldn't. — infernus-85, Sep 27 '21 at 08:12
This is called [`partition`](https://en.cppreference.com/w/cpp/algorithm/partition) in `std`, and the possible implementation on that site works for both `vector` and `list` (among others). Depending on the exact requirements, you might want [`stable_partition`](https://en.cppreference.com/w/cpp/algorithm/stable_partition) — Caleth, Sep 27 '21 at 08:14
@Caleth So, this would work on built in containers. A linked list defined using struct would not work. I guess the best way to do this would be to put the elements of a linked list into a vector and then run this algo on it and put it back. — infernus-85, Sep 27 '21 at 08:24
@infernus-85 you need to write an iterator type for your linked-list — Caleth, Sep 27 '21 at 08:27
([Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)) — Biffen, Sep 27 '21 at 10:44
Also [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Stef, Sep 27 '21 at 11:04
For a linked list, the problem would actually be easier than for arrays. Your algorithm is O(n**2); there is a O(n) simple solution for linked lists. — Stef, Sep 27 '21 at 11:09
@Stef can you share the algorithm? Also, I know the bad practices, but it's faster and I mostly code for contests. I need to be as fast s possible and write as less code as possible. — infernus-85, Sep 27 '21 at 12:29
@infernus-85 Actually, `using std::cout;` would have been faster than `using namespace std;` in that case. — Stef, Sep 27 '21 at 12:44
@infernus-85 With linked list, there is no "in-place" constraint; just add the elements to two distinct lists depending on whether they're smaller or larger than x, then add a link from the end of the "smalls" list to the start of the "larges" list. — Stef, Sep 27 '21 at 12:46
@Stef I wasn't supposed to use another linked list. That I thought of at first. But, I guess copying elements from linked list to vector doesn't break that constraint. — infernus-85, Sep 27 '21 at 13:03
@infernus-85 A linked list is a bunch of nodes with pointers. Just play around with the pointers; you don't need to allocate memory for new nodes. — Stef, Sep 27 '21 at 13:04
@Stef Ah, I see. So, you would copy the elements in an array and then fill the LL with the nodes which are smaller than 'x' and then after that you fill elements equal to or greater than 'x'? Right? (everything sequentially of course) — infernus-85, Sep 27 '21 at 13:07
No. I would not use any array. I think the whole point of the question is that you should not use any extra memory, except for a constant number of variables. No new arrays. — Stef, Sep 27 '21 at 13:10

score 1 · Accepted Answer · answered Sep 29 '21 at 12:50

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.

Given an array 'a' and an integer 'x', arrange the elements of the (in place) such that all the elements ='x'

1 Answers1