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