CC150 2.4

2_4.cpp

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

#include <iostream>
#include <list>

using namespace std;

void partition(list<int> &lst, int x)
{
	auto bound = lst.begin(), end = lst.end(); // bound indicates the boundary of partitions, points at the smaller element
	auto runner = bound;
	if (*runner >= x) { // find the first small element and move to the head
		while (runner != end && *runner >= x) ++runner;
		bound = lst.insert(bound, *runner);
		runner = lst.erase(runner);
	}
	else { // move bound to one element left to the first large element
		while (runner != end && *runner < x) ++runner;
		bound = runner;
		--bound;
	}
	while (runner != end) { // runner traverse through the list and move small elements before bound
		if (*runner >= x)
			++runner;
		else {
			bound = lst.insert(++bound, *runner);
			runner = lst.erase(runner);
		}
	}
	return;
}

void partition2(list<int> &lst, int x)
{
	list<int> small, large;
	for (auto i : lst) { // generate two extra lists, holding smaller and larger parts respectively
		if (i < x)
			small.push_back(i);
		else
			large.push_back(i);
	}
	lst.clear(); // cascatenate two lists together and replace the original list
	for (auto i : small)
		lst.push_back(i);
	for (auto i : large)
		lst.push_back(i);
	return;
}

int main()
{
	int x;
	cin >> x;
	list<int> lst;
	int data;
	while (cin >> data)
		lst.push_back(data);
	partition2(lst, x);
	for (auto i : lst)
		cout << i << " ";
	cout << endl;
	return 0;
}