Algorithm One Day One -- 判斷鏈表是否有環(huán)(上)
來源：程序員人生 發(fā)布時間：2015-01-28 08:45:51 閱讀次數(shù)：3180次
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)
{
//創(chuàng)建1個鏈表
Node *head,*tail,*cnew;
head=NULL;
int num;
cout <<"輸入數(shù)據(jù)(以#鍵結(jié)束):" << endl;
while(1 )
{
cin >>num ;
if('#'==getchar())
//以#鍵表示輸入結(jié)束
break;
cnew=new Node;;
cnew->data=num;
cnew->next=NULL;
if(head==NULL)
//若為空則將頭節(jié)點指向新節(jié)點
head=cnew;
else
tail->next=cnew;
//將當前節(jié)點的next指向新的節(jié)點
tail=cnew;
(*numNode)++;
}
return head;}
/*判斷是不是有環(huán)思路概述：分別定義步長為1和2的指針fast and slow
指向頭結(jié)點，if無環(huán)，則fast先走到終點；如果鏈表長度為奇數(shù)時，
fast->Next為空；當鏈表長度為偶數(shù)時，fast為空*/
bool isLoop(pNode pHead)
{
pNode fast = pHead;
pNode slow = pHead;
while( fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
//如果有環(huán)，則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;
//初始化將節(jié)點個數(shù)初始化為零
pNode head=NULL ;
cout <<"鏈表head的節(jié)點個數(shù)為: " <<endl;
cin >>numnode;
head=Create(&numnode);
isLoop(head);
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
