#include<iostream>usingnamespacestd;#include<assert.h>template<classT>structNode{int_data;Node*_next;Node(constT&x):_data(x),_next(NULL){}};template<classT>classPlinkList{public:PlinkList():_head(NULL){}voidPushBack(constT&x){if(_head==NULL){_head=newNode<T>(x);_tail=_head;}else{Node<T>*tmp=newNode<T>(x);Node<T>*cur=_head;while(cur->_next){cur=cur->_next;}tmp->_next=cur->_next;cur->_next=tmp;_tail=tmp;}}Node<T>*JosephusCycle(intk)//约瑟夫环问题{assert(_head);_tail->_next=_head;Node<T>*begin=_head;while(1){if(begin->_next==begin)break;intcount=k-1;while(count-->0){//del=begin;begin=begin->_next;}Node<T>*del=begin->_next;//swap(begin->_data,begin->_next->_data);begin->_next=del->_next;begin=begin->_next;deletedel;}returnbegin;}voidFind_comm(Node<T>*one,Node<T>*two)//找两个已排好序链表的相同数{assert(one&&two);Node<T>*cur1=one;Node<T>*cur2=two;while(cur1&&cur2){if(cur1->_data>cur2->_data)cur2=cur2->_next;elseif(cur1->_data<cur2->_data)cur1=cur1->_next;else{cout<<cur1->_data<<"";cur1=cur1->_next;cur2=cur2->_next;}}cout<<"notcommdata"<<endl;}Node<T>*Find_CenterNode()//查找链表的中间节点{assert(_head);Node<T>*slow=_head;Node<T>*fast=_head;while(fast&&fast->_next){slow=slow->_next;fast=fast->_next->_next;}returnslow;}booldel_thelast_Knode(intpos)//删除倒数第Pos个节点{intcount=0;Node<T>*cur=_head;while(cur){cur=cur->_next;count++;}if(pos<0||pos>count)returnfalse;if(pos==count)//如果要删除的为头结点{Node<T>*del=_head;_head=_head->_next;deletedel;returntrue;}/*else//采用快慢指针让快指针先走pos步，慢指针再走{Node<T>*slow=_head;Node<T>*fast=_head;Node<T>*prev=_head;intk=0;while(fast){if(k>=pos){prev=slow;slow=slow->_next;}fast=fast->_next;k++;}Node<T>*del=slow;prev->_next=del->_next;deletedel;returntrue;}*/else//也可走count-pos步并记录该位置的前一个位置{count=count-pos;intnum=0;Node<T>*prev=_head;Node<T>*tmp=prev;cur=_head;while(cur->_next){if(num+1==count){tmp=cur;cur=cur->_next;break;}cur=cur->_next;//prev=prev->_next;num++;}Node<T>*del=cur;tmp->_next=del->_next;deletedel;returntrue;}}Node<T>*reverse()//逆置单链表{assert(_head);if(_head->_next==NULL)return_head;Node<T>*cur=_head;Node<T>*newHead=NULL;while(cur){Node<T>*tmp=cur;cur=cur->_next;tmp->_next=newHead;newHead=tmp;}returnnewHead;}voidPrintTailTohead(Node<T>*head)//从尾到头打印单链表{if(head==NULL)return;else{PrintTailTohead(head->_next);cout<<head->_data<<"->";}}voidDisplay(){assert(_head);Node<T>*cur=_head;while(cur){cout<<cur->_data<<"->";cur=cur->_next;}cout<<"NULL"<<endl;}voidBubble_sort()//链表的冒泡排序{assert(_head);Node<T>*prev=_head;Node<T>*end=NULL;while(prev->_next)//控制排序次数{Node<T>*tmp=_head;while(tmp->_next!=end)//相邻两元素交换单趟排序{if(tmp->_data>tmp->_next->_data)swap(tmp->_data,tmp->_next->_data);tmp=tmp->_next;}end=tmp;prev=prev->_next;}}Node<T>*Quicksort(Node<T>*begin,Node<T>*end){Node<T>*prev=begin;Node<T>*cur=begin->_next;intkey=begin->_data;while(cur!=end){if(cur&&cur->_data<key){prev=prev->_next;if(prev->_data!=cur->_data)swap(prev->_data,cur->_data);}cur=cur->_next;}swap(begin->_data,prev->_data);returnprev;}voidQuick_sort(Node<T>*begin,Node<T>*end){if(begin!=end){Node<T>*tmp=Quicksort(begin,end);Quick_sort(begin,tmp);Quick_sort(tmp->_next,end);}}~PlinkList(){if(_head==NULL)return;Node<T>*cur=_head;while(cur){Node<T>*del=cur;cur=cur->_next;deletedel;}_head=NULL;}public:Node<T>*_head;Node<T>*_tail;};//voidTest()//{//PlinkList<int>l;//l.PushBack(8);//l.PushBack(3);//l.PushBack(7);//l.PushBack(1);//l.PushBack(9);//l.PushBack(6);//l.PushBack(0);//l.PushBack(5);////l.Display();////l.Quick_sort(l._head,NULL);////l.Bubble_sort();////l._head=l.reverse();////l.del_thelast_Knode(8);////cout<<l.Find_CenterNode()->_data<<endl;////l.PrintTailTohead(l._head);////cout<<"NULL"<<endl;//cout<<l.JosephusCycle(3)->_data<<endl;////l.Display();//}