1，制作环型链表

2。检測链表中是否存在环（）

3。计算链表中环的长度

4， 计算链表中环起始的位置

5，推断一个链表是否存在回文，要求O（n）时间和O（1）空间的复杂度（）

6。计算链表中间位置

7，链表原地反转（）

8，測试code

#include 
     
      using namespace std;/*	@1: detect if there is a circule in a list -> detect_circule_exist	@2: calculate the circule length in the list -> give_circ_len	@3: locate the place where the circule starts -> locate_circ_place	@4: detect if the list is palindrome -> time:o(n) and space:o(1)*//*	struct simple linked list*/struct item{	int n;	struct item *next;};class iter {	struct item *head;	int circ_len;public:	void insert(int i);	bool remove(int i);	iter(){this->circ_len = 0;this->head = new(struct item);this->head->next = NULL;}	bool create_circule(int i);	void remove_circule();	bool detect_circule_exist();	int give_circ_len();	int locate_circ_place();	bool detect_palindrome();	void display();	~iter();};void iter::insert(int i) {	struct item *cur;	struct item *add_item = new(struct item);	add_item->n = i;	add_item->next = NULL;	/* insert at tail */	cur = this->head;	while(cur->next) {		cur = cur->next;	}	cur->next = add_item;	cout << add_item <
      
       head->next, *prev = this->head;	while (cur) {		if (cur->n == i) {			prev->next = cur->next;			return true;		} else {			cur = cur->next;			prev = prev->next;		}	}	return false;}void iter::display(){	struct item *cur = this->head->next;	while (cur){		cout << cur->n << " -> ";		cur = cur->next;	}	cout <<"end" << endl;}/* create a circult at value: i, if not i exist return false*/bool iter::create_circule(int i){	struct item *cur = this->head;	struct item *find = NULL;	while (cur->next){		cur = cur->next;		if (cur->n == i) {			find = cur;		}	}	if (find) {		cur->next = find;		return true;	} else		return false;}/* detect if exist a circule in the linked list */bool iter:: detect_circule_exist(){	/*quick and slow point to the first element of the linked list*/	struct item *quick, *slow, *mark;	bool find = false;	slow = this->head->next;	quick = this->head->next->next;	while (quick && slow) {		if (!find) {			if (quick == slow) {				find = true;				mark = slow;				slow = slow->next;				this->circ_len++;			} else {				if (!quick->next || !quick->next->next)					break;				if (!slow->next)					break;				quick = quick->next->next;				slow = slow->next;			}		} else {			if (mark == slow) {				return true;			} else {				slow = slow->next;				this->circ_len++;			}		}	}	find = false;	return find;}int iter:: give_circ_len(){	this->detect_circule_exist();	return this->circ_len;}/* cal the len of non circule at the linked list */int iter:: locate_circ_place(){	if (this->detect_circule_exist()) {		struct item *quick, *slow;		int i = this->circ_len;		slow = this->head->next;		quick = this->head->next;		while (quick && i--) {			quick = quick->next;		}		i = 0;		while (quick && slow) {			if (quick == slow) {				return i;			} else {				i++;				quick = quick->next;				slow = slow->next;			}		}		} else {		return 0;	}}void iter:: remove_circule(){	struct item *tail = this->head;	struct item *mark;	int i = this->locate_circ_place() + 1;	while (tail->next && i--){		tail = tail->next;	}	mark = tail;	while (tail) {			if (tail->next == mark) {			tail->next = NULL;			return;		} else {			tail = tail->next;		}	}}bool iter:: detect_palindrome(){	struct item *quick, *slow;	/*first find the middle place of the linked list by quick and slow pointer*/	slow = this->head->next;	quick = this->head->next->next;	while (slow) {		struct item *mark;		slow = slow->next;		quick = quick->next->next;		if (!quick) {			/*reverse the linked list at the place*/			mark = slow;			quick = slow->next->next; /*q*/			slow = slow->next; /*p*/			struct item *temp;			while (quick) {				temp = quick->next;				quick->next = slow;				slow = quick;				quick = temp;			}			mark->next->next = NULL;			mark->next = slow;			slow = this->head->next;			mark = mark->next;			while (slow && mark) {				//cout << "odd first part: "<< slow->n << "addr:"  << slow << "second part: " << mark->n << "addr:" << mark <
       
        n != mark->n)					return false;				else {					slow = slow->next;					mark = mark->next;				}			}			return true;		}		if (!quick->next) {			/*reverse the linked list at the place*/			mark = slow;			quick = slow->next->next; /*q*/			slow = slow->next; /*p*/			struct item *temp;			while (quick) {				temp = quick->next;				quick->next = slow;				slow = quick;				quick = temp;			}			mark->next->next = NULL;			mark->next = slow;			slow = this->head->next;			mark = mark->next;			while (slow && mark) {				//cout << "even first part: "<< slow->n << "addr:"  << slow << "second part: " << mark->n << "addr:" << mark <
        
         n != mark->n)					return false;				else {					slow = slow->next;					mark = mark->next;				}			}			return true;		}	}}iter::~iter(){	struct item *cur = this->head->next;	if (this->detect_circule_exist())		this->remove_circule();	while (cur){		struct item *temp = cur;		cur = cur->next;		delete temp;		//cout <<"delete" << temp<< endl;	}	delete this->head;}int main(){	class iter myiter;	/*	for (int i = 0; i < 10; i++) {		myiter.insert(i);	}	myiter.create_circule(2);		if (myiter.detect_circule_exist())		cout << "detect circule exist and circ len" << myiter.give_circ_len()<< endl;	else		cout << "no detect circule exist" <