学步园

 这个类是几个功能的集合类，注意在制造出环后，判断出有环，之后应该拆除环，否则最后链表的析构函数将因为有环的存在而无法正常退出，将会导致程序四循环。

#include<iostream><br /> using namespace std;<br /> struct ListNode<br /> {<br /> int data;<br /> ListNode *next;<br /> };<br /> class LinkList<br /> {<br /> ListNode *head; //指向链表的头指针<br /> int count; //结点数目<br /> ListNode *interP; //存放制造环时的中间节点<br /> public:<br /> LinkList();<br /> LinkList(int n); //手动创建一个含有n个元素的链表<br /> ~LinkList();<br /> void ReverseList(); //逆序链表<br /> void PrintList(); //打印当前的链表<br /> bool IsCircle(); //判断链表中是否有环<br /> //制造环——方法是将链尾指向链中第n个节点后面(条件:count>n)<br /> void GeneCircle(int n);<br /> void DegeneCircle(int n); //拆环，防止不能析构<br /> };<br /> LinkList::LinkList()<br /> {<br /> head = NULL;<br /> count = 0;<br /> }<br /> LinkList::LinkList(int n)<br /> {<br /> count = n;<br /> head = new ListNode;<br /> ListNode *p = head;<br /> for(int i=0;i<n;i++)<br /> {<br /> ListNode *newPtr = new ListNode; //新建一个结点<br /> cout<<"Input Node "<<i+1<<": ";<br /> cin>>newPtr->data; //新节点赋值<br /> p->next = newPtr; //当前结点指向newPtr<br /> p = p->next; //p变为当前位置的下一个位置<br /> }<br /> p->next =NULL;<br /> interP = NULL;<br /> }<br /> LinkList::~LinkList()<br /> {<br /> ListNode *p = head->next;<br /> ListNode *tmpPtr;<br /> while(p != NULL)<br /> {<br /> tmpPtr = p->next;<br /> delete p;<br /> p = tmpPtr;<br /> }<br /> delete tmpPtr,p,head,interP;<br /> p = tmpPtr = head = interP = NULL;<br /> cout<<"Deconstructor!"<<endl;<br /> }<br /> void LinkList::ReverseList()<br /> {<br /> ListNode *pCurr = head->next; //pCurr指向待逆序链表的表头结点(即p指向第一个节点)<br /> if(pCurr == NULL || pCurr->next == NULL) //只有头指针或者只有一个节点<br /> return ;<br /> head->next = NULL; //清空原链表(head仍为逆序后的表头结点)<br /> //将原链表中的结点依次进行逆序链接<br /> while(pCurr != NULL)<br /> {<br /> ListNode *pTmp = pCurr->next; //pCurr指向待处理的结点,pTmp存放pCurr的下一个节点<br /> //将pCurr插入到head和第一个节点之间(即将pCurr作为新的第一个结点)<br /> pCurr->next = head->next; //将新的待处理的节点pCurr插入到原先第一个节点(head->next)之前<br /> head->next = pCurr; //头结点指向新的节点pCurr<br /> pCurr = pTmp; //下一个待处理结点<br /> }<br /> }<br /> void LinkList::PrintList()<br /> {<br /> if(count == 0)<br /> {<br /> cout<<"List is empty!"<<endl;<br /> return;<br /> }<br /> ListNode *p = head->next;<br /> cout<<"data of the List is:"<<endl;<br /> while(p != NULL)<br /> {<br /> if(p->next)<br /> cout<<p->data<<"-->";<br /> else<br /> cout<<p->data;<br /> p = p->next;<br /> }<br /> cout<<endl<<"length of the list is: "<<count<<endl;<br /> }<br /> bool LinkList::IsCircle()<br /> {<br /> ListNode *p = head->next;<br /> ListNode *q = head->next;<br /> while(p->next && q->next)<br /> {<br /> p = p->next;<br /> if(NULL == (q = q->next->next))<br /> return false;<br /> if(p == q)<br /> return true;<br /> }<br /> return false;<br /> }<br /> void LinkList::GeneCircle(int n)<br /> {<br /> if(n >= count)<br /> {<br /> cout<<"can not generate a circle!"<<endl;<br /> return;<br /> }<br /> ListNode *temp,*p = head->next; //p将要指向第n个（队尾）元素<br /> for(int i=1;p->next;i++)<br /> {<br /> if(i == n) //找到第n个元素<br /> {<br /> temp = p; //先用temp暂存第n个元素的指针p<br /> break;<br /> }<br /> p = p->next; //p不断指向后面的元素<br /> }<br /> interP = p->next;<br /> p->next = temp; //p的下一个元素指向temp（暂存原先p指向的元素），这样就形成了一个环<br /> }<br /> void LinkList::DegeneCircle(int n)<br /> {<br /> ListNode *p = head->next;<br /> for(int i=1;p->next;i++)<br /> {<br /> if(i == n)<br /> break;<br /> p = p->next;<br /> }<br /> p->next = interP;<br /> }<br /> int main()<br /> {<br /> int N,pos;<br /> cout<<"Input length of the List: ";<br /> cin>>N;<br /> LinkList ls(N);<br /> ls.PrintList();<br /> ls.ReverseList();<br /> ls.PrintList();<br /> ls.ReverseList();<br /> ls.PrintList();<br /> cout<<"Input the position where to generator circle:";<br /> cin>>pos;<br /> ls.GeneCircle(pos);<br /> if(ls.IsCircle())<br /> {<br /> cout<<"Circle Linklist!"<<endl;<br /> //必须使用这个函数恢复链为无环状态，否则因为环的存在，<br /> //链表的析构函数不能正常退出，导致程序死循环<br /> ls.DegeneCircle(pos);<br /> }<br /> else<br /> cout<<"Non-Circle LinkList!"<<endl;<br /> return 0;<br /> }
 

判断两个单链表是否相交
，如果相交，给出相交的第一个

点（两个链表都不存在环）

两个链表相交的意思是——从相交点开始往后的所有的节点都是重合的，类似一个"人"字。

比较好的方法有两个：

（一）将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

（二）如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。

       这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

第2种方法的代码如下：

NODE* FindNode(NODE* pHead1, NODE* pHead2)<br /> {<br /> NODE* p1 = pHead1;<br /> NODE* p2 = pHead2;<br /> int i = 1, j = 1, k = 0, f = 0;<br /> if(pHead1 == NULL || pHead2 == NULL)<br /> return NULL;<br /> while(p1->next != NULL)<br /> {<br /> p1 = p1->next;<br /> i++;<br /> }<br /> while(p2->next != NULL)<br /> {<br /> p2 = p2->next;<br /> j++;<br /> }<br /> if(p1 != p2)<br /> return NULL;<br /> else<br /> {<br /> p1 = pHead1;<br /> p2 = pHead2;<br /> f = fabs(i-j)<br /> if(i > j)<br /> {<br /> for(k=0; k<f; k++)<br /> p1 = p1->next;<br /> while(p1 != p2)<br /> {<br /> p1 = p1->next;<br /> p2 = p2->next;<br /> }<br /> return p1;<br /> }<br /> else<br /> {<br /> for(k=0; k<f; k++)<br /> p2 = p2->next;<br /> while(p1 != p2)<br /> {<br /> p1 = p1->next;<br /> p2 = p2->next;<br /> }<br /> return p1;<br /> }<br /> }<br /> }<br />