计算一个单项链表(链表中有环)中环的长度
这个方法用到了快指针和慢指针,他俩从头结点一起跑,每次快指针走两个节点,慢指针走一个节点,当进入环之后,快指针终会追上慢指针。这时,记录相遇的节点,然后让慢指针再跑一圈就可以测出环的长度了。
创新互联公司成立以来不断整合自身及行业资源、不断突破观念以使企业策略得到完善和成熟,建立了一套“以技术为基点,以客户需求中心、市场为导向”的快速反应体系。对公司的主营项目,如中高端企业网站企划 / 设计、行业 / 企业门户设计推广、行业门户平台运营、app软件开发、成都手机网站制作、微信网站制作、软件开发、成都温江机房等实行标准化操作,让客户可以直观的预知到从创新互联公司可以获得的服务效果。
这个方法适用于任何情况,无论整个链表都是环,还是环的节点只有一个的。
#include
#include
typedef struct node
{
int num;
struct node* next;
}NODE;
NODE* create(NODE* phead,int nu)
{
NODE* tmp = malloc(sizeof(struct node));
tmp->num = nu;
NODE* find = phead;
if(phead == NULL){
return tmp;
}
else{
while(find->next != NULL)
find = find->next;
find->next = tmp;
return phead;
}
}
void show(NODE* phead)
{
int i=0;
while(i<25){
printf("%d ",phead->num);
phead = phead->next;
i++;
}
printf("\n");
#if 0
while(phead){
printf("%d ",phead->num);
phead = phead->next;
}
printf("\n");
#endif
}
void createring(NODE* phead, NODE* point)
{
while(phead->next != NULL)
phead = phead->next;
phead->next = point;
}
NODE* point(NODE* phead)
{
while(phead->next != NULL)
phead = phead->next;
return phead;
}
void check(NODE* phead)
{
NODE* quick = phead;
NODE* slow = phead;
NODE* point = NULL;
NODE* point1 = phead;
int num = 0;
int num1 = 0;
while(1){
quick = quick->next->next; //快指针一次走两个
slow = slow->next; //慢指针一次走一个
if(slow == quick){
point = slow;
point = point->next; //记录当两个指针相遇时的位置,从这个位置开始计数,当指针转一圈时结束
num++;
while(slow != point){
point = point->next;
num++;
}
printf("链表中环的长度为: %d\n",num);
break;
}
}
while(1){ //当快慢指针在环中相遇时,一个新的指针从头结点向后走,慢指针继续走时,这两个指针就会相遇在入环的节点中。(这个规律为什么会这样,我也不知道,哪位大神知道,麻烦在评论区解释一下。)
if(point1 == point)
break;
point1 = point1->next;
point = point->next;
num1++;
}
printf("此链表的长度为:%d\n",num1+num);
}
NODE* createlian(NODE* head)
{
NODE* poin = NULL;
head = create(head,21);
create(head,22);
create(head,23);
create(head,24);
create(head,25);
create(head,26);
poin = point(head); //记录从环开始的节点
create(head,27);
create(head,28);
create(head,29);
create(head,30);
create(head,31);
create(head,32);
create(head,33);
createring(head,poin); //让尾节点指向环开始的节点
printf("这个链表为:\n");
show(head);
return head;
}
int main(void)
{
NODE* head;
NODE* tail;
NODE* poin;
NODE* head1;
head = createlian(head);
check(head);
// show(head);
return 0;
}
文章标题:计算一个单项链表(链表中有环)中环的长度
网站URL:http://pwwzsj.com/article/gghjhs.html