Partition a linked list such that all values lesser than a specific value (say, x) appear before and all values greater than or equal to x appear later.
`/*`
` * PartitionLinkedList.cpp`
` *`
` *  Created on: Apr 19, 2012`
` *      Author: Kiran Hegde`
` */`

`#include <iostream>`
`#include <cstdlib>`
`#include <time.h>`

`using namespace std;`

`struct Node {`
`    int data;`
`    Node *next;`
`};`

`/**`
` * Generate a linked list of length "size" containing random numbers from 1 to 10`
` */`
`Node *createLinkedList(int size) {`
`    srand(time(NULL));`
`    Node *head = NULL;`
`    for (int i = 0; i < size; i++) {`
`        Node *node = new Node;`
`        node->data = rand() % 10 + 1;`
`        node->next = head;`
`        head = node;`
`    }`
`    return head;`
`}`

`void deleteLinkedList(Node *head) {`
`    while (head != NULL) {`
`        Node *temp = head;`
`        head = head->next;`
`        delete temp;`
`    }`
`}`

`void printLinkedList(Node *head) {`
`    Node *curr = head;`
`    while (curr != NULL) {`
`        cout << curr->data << "-->";`
`        curr = curr->next;`
`    }`
`    cout << "EMPTY" << endl;`
`}`

`/**`
` * First split the linked list into two lists, one containing values`
` * less than partition, the other containing values greater than or equal to`
` * partition.  Then merge the two lists`
` */`
`void partitionLinkedList(Node *&head, int partitionValue) {`
`    Node *front = NULL;`
`    Node *back = NULL;`
`    Node *curr = head;`
`    while (curr != NULL) {`
`        Node *next = curr->next;`
`        if (curr->data < partitionValue) {`
`            curr->next = front;`
`            front = curr;`
`        }`
`        else {`
`            curr->next = back;`
`            back = curr;`
`        }`
`        curr = next;`
`    }`
`    //Move to end of front list`
`    curr = front;`
`    while (curr->next != NULL) {`
`        curr = curr->next;`
`    }`
`    //Merge the two lists`
`    curr->next = back;`
`    //change the head pointer`
`    head = front;`
`}`

`/**`
` * Test the function`
` */`
`int main() {`
`    Node *head = createLinkedList(15);`
`    cout << "Original List: " << endl;`
`    printLinkedList(head);`
`    partitionLinkedList(head, 5); //Partition at value 5`
`    cout << "List After Partitioning: " << endl;`
`    printLinkedList(head);`
`    deleteLinkedList(head);`
`    return 0;`
`}`