Partition a linked list
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;
}