2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before alt nodes greater than or equal to x.

2.4.cpp

#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
    
    Node(int data, Node *next) {
        this->data = data;
        this->next = next;
    }
    
    ~Node() {}
};

typedef Node* pNode;

void print(Node * head)
{
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

void clear(Node *head)
{
    if (head != nullptr) {
        while(head->next != nullptr) {
            Node *t = head->next;
            head->next = t->next;
            delete t;
        }
        delete head;
    }
}

pNode partition(pNode head, decltype(head->data) x)
{
    pNode beforeBegin{}, beforeEnd{}, afterBegin{}, afterEnd{};
    
    while (head != nullptr) {
        if (head->data < x) {
            if (beforeBegin == nullptr)
                beforeBegin = head;
            if (beforeEnd != nullptr)
                beforeEnd->next = head;
            beforeEnd = head;
            head = head->next;
            beforeEnd->next = nullptr;
        } else if (head->data == x) {
            if (afterEnd == nullptr)
                afterEnd = head;
            pNode p = afterBegin;
            afterBegin = head;
            head = head->next;
            afterBegin->next = p;
        } else {
            if (afterBegin == nullptr)
                afterBegin = head;
            if (afterEnd != nullptr)
                afterEnd->next = head;
            afterEnd = head;
            head = head->next;
            afterEnd->next = nullptr;
        }
    }
    
    if (beforeBegin == nullptr)
        beforeBegin = afterBegin;
    else
        beforeEnd->next = afterBegin;
    
    return beforeBegin;
}

pNode partition1(pNode head, decltype(head->data) x)
{
    pNode beforeBegin{}, beforeEnd{}, afterBegin{}, afterEnd{};
    
    while (head != nullptr) {
        pNode next = head->next;
        head->next = nullptr;
        if (head->data < x) {
            if (beforeBegin == nullptr) {
                beforeBegin = head;
                beforeEnd = head;
            } else {
                beforeEnd->next = head;
                beforeEnd = head;
            }
        } else if (head->data == x) {
            head->next = afterBegin;
            afterBegin = head;
            if (afterEnd == nullptr)
                afterEnd = afterBegin;
        } else {
            if (afterBegin == nullptr) {
                afterBegin = head;
                afterEnd = head;
            } else {
                afterEnd->next = head;
                afterEnd = head;
            }
        }
        head = next;
    }
    
    if (beforeBegin == nullptr)
        return afterBegin;
    
    beforeEnd->next = afterBegin;
    return beforeBegin;
}

pNode partition2(pNode head, decltype(head->data) x)
{
    pNode beforeBegin{}, afterBegin{};
    
    while (head != nullptr) {
        pNode next = head->next;
        if (head->data < x) {
            head->next = beforeBegin;
            beforeBegin = head;
        } else {
            head->next = afterBegin;
            afterBegin = head;
        }
        head = next;
    }
    
    if (beforeBegin == nullptr)
        return afterBegin;
    
    pNode e = beforeBegin;
    while (e->next != nullptr)
        e = e->next;
    e->next = afterBegin;
    return beforeBegin;
}

int main(int argc, char *argv[])
{
    Node *list = new Node(4, new Node(3, new Node (2, new Node(1, new Node(0, nullptr)))));
    print(list);
    list = partition2(list, 2);
    print(list);
    clear(list);
    return 0;
}