程序员人生 网站导航

Algorithm One Day One -- 判断链表是否有环(上)

栏目:综合技术时间:2015-01-28 08:45:51


Is a loop ? Question descrip as follows :

        Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register?

/******************************************************************** created:2015年1月22日 00:54:56 author: Jackery purpose: Is there a loop ? *********************************************************************/ #include"stdafx.h" #include<iostream> using namespace std; typedef struct node { int data; struct node *next; }Node,*pNode; Node *Create(int *numNode) { //创建1个链表 Node *head,*tail,*cnew; head=NULL; int num; cout <<"输入数据(以#键结束):" << endl; while(1 ) { cin >>num ; if('#'==getchar()) //以#键表示输入结束 break; cnew=new Node;; cnew->data=num; cnew->next=NULL; if(head==NULL) //若为空则将头节点指向新节点 head=cnew; else tail->next=cnew; //将当前节点的next指向新的节点 tail=cnew; (*numNode)++; } return head;} /*判断是不是有环思路概述:分别定义步长为1和2的指针fast and slow 指向头结点,if无环,则fast先走到终点;如果链表长度为奇数时, fast->Next为空;当链表长度为偶数时,fast为空*/ bool isLoop(pNode pHead) { pNode fast = pHead; pNode slow = pHead; while( fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; //如果有环,则fast会超过slow1圈 if(fast == slow) { break; } } if(fast == NULL || fast->next == NULL ) { cout <<"Wow,there is not loop in the list "<< endl; return false; } else { cout <<"Yeah,there is loop in the list " << endl; return true; } } int main(int argc ,char * argv[]) { int numnode=0; //初始化将节点个数初始化为零 pNode head=NULL ; cout <<"链表head的节点个数为: " <<endl; cin >>numnode; head=Create(&numnode); isLoop(head); return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐