单向链表相关
单向链表是微软笔试常考的，参考这里：http://www.cnblogs.com/tdyizhen1314/archive/2012/04/03/2431124.html
?
#include<iostream>using namespace std;struct node{ int data; struct node* next;};//定义一个名字呢 node* create(unsigned int n){ if(n==0){ cout<<"ensure n>0. (create failure)"<<endl; return NULL; } //assert(n>0); node* head=new node;//new一个struct cout<<"#1:"; cin>>head->data; head->next=NULL; int i; node *pre=head; node *cur=NULL; for(i=1;i<n;i++){ cur=new node; cout<<"#"<<i+1<<":"; cin>>cur->data; cur->next=NULL; pre->next=cur; pre=cur; } return head;}/*node* reverse(node* list){ node* one=list; node* two=NULL; node* three=NULL; if(list->next!=NULL) two=list->next; else return list; if(list->next->next!=NULL) three=list->next->next; one->next=NULL; while(two!=NULL){ two->next=one; one=two; two=three; if(three!=NULL) three=three->next; else break; } return one;}*//*问题1：链表反转 思路：head指针不断后移，指针反向即可*/void reverse(node*& head){ /*1. 先讨论空链表和只有一个节点的情况*/ if(head==NULL) return; if(head->next==NULL) return; /*2. 在处理普通情况*/ node* p=head; node* q=head->next; while(q!=NULL){ node* temp=q->next; q->next=p; p=q; q=temp; } head->next=NULL; //反转前的链表头特殊处理 head=p;}/*问题2：删除不知头结点链表的某个节点如果单向链表不知道头节点，一个指针指向其中的一个节点，问如何删除这个指针指向的节点 思路：下一个节点的值复制给该节点，然后删除下一个节点即可 */void deleteNodeInList(node*& n){ if(n==NULL) return; if(n->next==NULL){ delete n; n=NULL; return; } /*一般情况：存在下一个节点*/ node* nextNode=n->next; n->data=nextNode->data; n->next=nextNode->next; delete nextNode;} /* 问题3：判断链表中是否有环 思路： 设置两个指针，一个步长为1，另一个步长为2，依次后移，如果相遇且都不为空，则有环。 解释： que:跑步能追上确实很容易理解。但问题是，跑步是连续的，而这里不是。因为有一个指针是跳两步的，不是连续的，怎么证明这样也肯定能碰上；好像只能证明一定能超过啊ans:画上一个圈就知道啦!速度快的开始肯定会超过慢的.一个步长1（乌龟），另外一个步长2（兔子），因此兔子一次追上1个单位,如果确实是个圈的话肯定会追上并且是相遇在同一个单位之内! */node* hasLoop(node* head){ //返回第一次交汇的点（能写成输入参数吗） if(head==NULL) return NULL; if(head->next==NULL) return NULL; /*至少有2个节点的单链表*/ node* p=head; node* q=head; while(true){ if(p==NULL || q==NULL) return NULL; if(p->next==NULL || q->next==NULL) return NULL; if(q->next->next==NULL) return NULL; //p步长为1后移 p=p->next; //q步长为2后移 q=q->next->next; //如果p,q重合在非NULL节点，则有环 if(p==q && p!=NULL){ return p; } }}/* 问题4：找出环的入口节点 思路： 当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：2s = s + nr <==> s= nr设入口环与相遇点距离为x，x<r，起点到环入口点的距离为a.a = s - x = (n-1)r+ (r-x), 而r-x即为fast再次到环入口点时的步数由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。 */node* getLoopHead(node* list){ node* inter; //第一次交汇点 if( (inter=hasLoop(list)) !=NULL ){ node* p=list; while(true){ if(p==inter) return p; p=p->next; inter=inter->next; } } return NULL;}/* 问题5：找出倒数第k个节点 */node* findLastK(node* head, unsigned int k){ /* back指向开始处, front指向前于它(k-1)个位置处 */ node* back=head; node* front=head; for(int i=1;i<k;i++){ if(front==NULL) return NULL; front=front->next; } if(front==NULL) return NULL; /* 后移 */ while(front->next){ back=back->next; front=front->next; } return back;}/* 问题6： 《编程之美》 3.6 判断两个链表是否相交 */void traverse(node* list){ if(list==NULL) return; cout<<list->data<<"\t"; while(list->next!=NULL){ list=list->next; cout<<list->data<<"\t"; } cout<<endl;}int main(){ cout<<"****************创建****************"<<endl; node* list=create(6); traverse(list); /* cout<<"****************反转****************"<<endl; reverse(list); traverse(list); node* list2=create(2); traverse(list2); reverse(list2); traverse(list2); node* list3=create(1); traverse(list3); reverse(list3); traverse(list3); node* list4=create(0); cout<<"****************删除孤立节点****************"<<endl; deleteNodeInList(list->next->next); traverse(list); cout<<"**************** 检测环 | 找出环的入口节点 ****************"<<endl; if(hasLoop(list)==NULL) cout<<"无环"<<endl; else cout<<"有环"<<endl; //奇数(3)长度环 node* n1=new node; node* n2=new node; node* n3=new node; node* n4=new node; n1->data=1; n2->data=2; n3->data=3; n4->data=4; n1->next=n2; n2->next=n3; n3->next=n4; n4->next=n2; if(hasLoop(n1)==NULL) cout<<"无环"<<endl; else cout<<"有环"<<endl; node* inter=getLoopHead(n1); cout<<"环入口: "<<inter->data<<endl; delete n1; delete n2; delete n3; delete n4; //偶(2)长度环 n1=new node; n2=new node; n3=new node; n4=new node; n1->data=1; n2->data=2; n3->data=3; n4->data=4; n1->next=n2; n2->next=n3; n3->next=n4; n4->next=n3; if(hasLoop(n1)==NULL) cout<<"无环"<<endl; else cout<<"有环"<<endl; inter=getLoopHead(n1); cout<<"环入口: "<<inter->data<<endl; delete n1; delete n2; delete n3; delete n4;*/ cout<<"****************寻找倒数第k个节点****************"<<endl; node* last0=findLastK(list,0); cout<<last0->data<<endl; node* last1=findLastK(list,1); cout<<last1->data<<endl; node* last3=findLastK(list,3); cout<<last3->data<<endl; node* last4=findLastK(list,4); cout<<last4->data<<endl; system("pause"); return 0;}