//快排，冒泡链表排序
#include
#include
using namespace std;
template
struct LinkNode
{
	T _data;
	LinkNode* _next;
	LinkNode(const T& x)
		:_data(x)
		, _next(NULL)
	{}
};
template
class ListNode
{
	//为了安全性
private:
	ListNode(const ListNode& l)
	{}
	ListNode& operator=(ListNode l)
	{}
public:
	//程序限制
	LinkNode* _head;
public:
	ListNode()
		:_head(NULL)
	{}
	~ListNode()
	{
		while (_head)
		{
			PopBack();
		}
	}
	void PushBack(const T& x)
	{
		LinkNode* tmp = new  LinkNode(x);
		if (_head == NULL)
			_head = tmp;
		else
		{
			LinkNode* cur = _head;
			while (cur->_next)
				cur = cur->_next;
			cur->_next = tmp;
		}
	}
	void PopBack()
	{
		if (_head == NULL)
			return;
		if (_head->_next == NULL)
		{
			delete _head;
			_head = NULL;
		}
		else
		{
			LinkNode* cur = _head;
			while (cur->_next&&cur->_next->_next)
			{
				cur = cur->_next;
			}
			LinkNode* del = cur->_next;
			cur->_next = NULL;
			delete del;
		}
	}
	LinkNode* Search(const T& x)
	{
		if (_head == NULL)
			return  NULL;
		LinkNode*  cur = _head;
		while (cur->_data != x)
			cur = cur->_next;
		return cur;
	}
	void Print()
	{
		LinkNode* cur = _head;
		while (cur)
		{
			cout << cur->_data << " ";
			cur = cur->_next;
		}
		cout << endl;
	}
};
template
LinkNode* QuickPartion(LinkNode* begin,LinkNode* end)//前闭后开
{
	if (begin== end)
		return  begin;
	LinkNode* prev,* cur;
	prev = begin;
	cur = begin->_next;
	int tmp = begin->_data;
	while (cur != end)
	{
		if(cur->_data < tmp)
		{
			prev = prev->_next;
			if (cur!=prev)
				swap(cur->_data, prev->_data);
		}
		cur = cur->_next;
	}
	swap(prev->_data, begin->_data);
	return prev;
}
template
void QuickSort(LinkNode* head,LinkNode* tail)
{
	if (head == NULL || head-== tail)
		return;
	LinkNode* mid = QuickPartion(head, tail);
	QuickSort(head, mid);
	QuickSort(mid->_next, tail);
}
template
void BubbleSort(LinkNode* head)
{
	if (head == NULL || head->_next == NULL)
		return;
	LinkNode* start = head;
	LinkNode* end = NULL;
	LinkNode* curBegin = NULL;
	int flag = 0;
	while (start->_next)
	{
		curBegin = start;
		flag = 0;
		while (curBegin->_next != end)
		{
			if (curBegin->_data > curBegin->_next->_data)
			{
				swap(curBegin->_data, curBegin->_next->_data);
				flag = 1;
			}
			curBegin = curBegin->_next;
		}
		if (flag == 0)
			break;//优化,若有序，直接跳出
		end = curBegin;
	}
}
template
LinkNode* SearchMidNode(LinkNode* head)
{
	if (head == NULL || head->_next == NULL)
		return head;
	LinkNode* slow = head;
	LinkNode* fast = head;
	while (fast&&fast->_next)//偶数个数中间任意一个
	//while (fast&&fast->_next&&fast->_next->_next)//偶数个数找到中间的第一个
	{
		fast = fast->_next->_next;
		slow = slow->_next;
	}
	return slow;
}
void Test1()
{
	ListNode l1;
	l1.PushBack(10);
	l1.PushBack(9);
	l1.PushBack(8);
	l1.PushBack(7);
	l1.PushBack(6);
	l1.PushBack(6);
	l1.PushBack(5);
	l1.PushBack(9);
	l1.PushBack(0);
	l1.PushBack(1);
	l1.PushBack(2);
	/*LinkNode* tail = NULL;
	QuickSort(l1._head,tail);*/
	//BubbleSort(l1._head);
	cout << SearchMidNode(l1._head)->_data<< endl;
	l1.Print();
}

新闻名称：单链表的排序（快排和冒泡实现）以及查找中间结点
分享URL：http://cdweb.net/article/peipic.html