clist.cpp

生成一个单向链表（*pListHead） 用C中的结构体或C++中的类实现 完成基本要求 基本算法要求： 实现对链表的逆序 void reverse（CList& ）； 查找

#include "CList.h"
#include <iostream>
using namespace std;
struct ListNode;
CList::CList()
{
	pListHead = NULL;
}
CList::~CList()
{

}
void CList::add(ListNode* pnode)
{
	ListNode* tmp;
	tmp = pListHead;
	pListHead = pnode;
	pnode->next = tmp;
}
void CList::reverse()
{
	if (this->isCircled()==true)
	{
		return;//如果有环 反转不能成功
	}
	ListNode* p = pListHead;
	ListNode* q = NULL;
	ListNode* t = pListHead;
	while (p != NULL)
	{
		t = p->next;
		p->next = q;
		q = p;
		p = t;
	}
	pListHead = q;

}
void CList::display()
{
	ListNode* tmp = pListHead;
	while (tmp!=NULL)
	{
		cout<<tmp->data<<' ';
		tmp = tmp->next;
	}
}
ListNode* CList::FindFBack(int k){
	this->reverse();
	ListNode* tmp = pListHead;
	for (int i=1;i<k;i++)
	{
		if (tmp == NULL)
		{
			return NULL;
		}
		tmp = tmp->next;
	}
	this->reverse();
	return tmp;
}
bool CList::isCircled()
{
	/*假设步长为a,b，进入圈之前长度为m，圈长n，实际上，不论步长为多少（只要不相同），圈内相遇的步数都不会超过n步，
	双方都进入圈需要：m/min{a,b}步 
	最差情况下圈内相遇的步数：n/最大公约数{a,b,n} 
	事实上，因为n是随机的，因此圈内相遇的步数也是随机的，不可控制，但上限是n步，所以应该尽量减小双方进入圈需要的步数，
	所以a,b越大越好，但又产生了另外一个问题，就是步长越长，走一步所花的时间就越长，所以是两难！*/
	
	
	
	if (pListHead==NULL)
	{
		return false;
	}
	if (pListHead->next==pListHead)
	{
		return true;
	}
	else if (pListHead->next==NULL)
	{
		return false;
		
	}
	
	ListNode* s = pListHead;
	ListNode* t = pListHead->next;
	while (s!=t)
	{
		if (t==NULL || t->next==NULL||s==NULL  )
		{
			return false;
		}
		t = t->next->next;
		s = s->next;
	}
	return true;
}
void CList::order()
{
	//递增
	if (this->isCircled()==true)
	{
		return;//如果存在环，不能排序
	}
	int nNodes = length();
	ListNode** sortList = new ListNode*[nNodes];
	ListNode* tmp = pListHead;
	int i;
	for (i=0;tmp!=NULL;i++)
	{
		sortList[i]=tmp;
		tmp =tmp->next;
	}

	//insertion sort
	int j,p;

	for (p=1;p<nNodes;p++)
	{
		tmp = sortList[p];
		for (j=p;j>0 && sortList[j-1]->data > tmp->data;j--)
		{
			sortList[j]=sortList[j-1];
		}
		sortList[j]=tmp;
	}

	pListHead = sortList[0];
	tmp = pListHead;
	for (i=1;i<nNodes;i++)
	{
		tmp->next = sortList[i];
		tmp = tmp->next;
	}
	sortList[nNodes-1]->next = NULL;
	delete sortList;
}
int CList::length()
{
	int i;
	ListNode* t = pListHead;
	for (i=0;t!=NULL;i++)
	{
		t = t->next;
	}
	return i;
}