下面小编为大家带来判断单链表中是否有环，计算出环的首地址 C语言实现，本文共2篇，希望能帮助大家!本文原稿由网友“dddd只不想秃头”提供。
篇1：判断单链表中是否有环，计算出环的首地址 C语言实现
判断单链表中是否有环,如果有,得出进入环时首个节点的地址.
有环的定义是，链表的尾节点指向了链表中的某个节点，
如: ____________
↓ ↑
①->②->③->④->⑤->⑥
那么要判断单链表中是否有环，主要有以下两种方法：
方法一：使用p1、p2两个指针指向头节点，p1总是向前走，但p2每次都从头开始走，对于每个节点，看p1走的步数是否和p2一样。如图，当p1从6走到3时，用了6步，此时若p2从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。而且这个点就是进入环时首个节点。(参考函数Plink check_link_1(Plink head))
方法二：使用p1、p2两个指针指向头节点，p1每次向前走一步，p2每次向前走两步，若在某个时候p1 == p2，则存在环。然后p2指向头结点，使p1,p2每次向前走一步，进行比较p1,p2如果p1==p2那么这个节点就是入环时首个节点。
算法如下:如上图所示，如果①节点到③节点的距离为x,假设第一次移动时，p1 == p2时的节点是⑤的话，③到⑤的距离为y, ③到的距离为z。 所以我们可以得到第一次p1==p2时，那么p1和p2走的步数的差就是p1走过的步数，而且是z的倍数。x+y+mz=nz,所以x+y=(m-n)z。所以当x+y向前移动x时肯定会到达入环时首个节点。 x+y+x=(m-n)z+x。这样我们就可以求得入环首节点的的地址了。(参考函数Plink check_link_1(Plink head))
代码如下所示:
/* * 判断单链表中是否有环,如果有,得出进入环节点的首地址. */#include #include typedef struct link{ int data; struct link *next;}*Plink;#define LINK_MAX 10/* 创建一个单链表 */void create_link(Plink *head, int num){ Plink node=NULL; Plink next=NULL; if(*head == NULL){ *head = (Plink)malloc(sizeof(struct link)); if(*head == NULL){ exit(0); } (*head)->data = num; (*head)->next = NULL; return; } node = *head; while(node->next != NULL){ node = node->next; } next = (Plink)malloc(sizeof(struct link)); if(next == NULL){ exit(0); } next->data = num; next->next = NULL; node->next = next; return;}/* 在单链表中设定一个环，让尾节点指向链表中的第n个节点 */int create_loop(Plink *head, int n){ int count=1; Plink node = *head; Plink n_node = NULL; if(head == NULL){ return -1; } while(node->next != NULL){ if(count == n){ n_node = node; } node = node->next; count++; } /* 尾节点和自身成一个环时 */ if(count == n){ n_node = node; } if(n_node == NULL){ return -1; } node->next = n_node; return 0;}/* 打印链表的前n个data的值 */void print_link(Plink head, int n){ int count=0; Plink node = head; while((node != NULL) && (count < n)){ printf(“%d->”, node->data); node = node->next; count++; } printf(“\\n”); return;}/* * 使用p1、p2两个指针，p1总是向前走，但p2每次都从头开始走， * 对于每个节点，看p1走的步数是否和p2一样，数不等，存在环。 * 而且该点就是入环时首个节点的地址。 */Plink check_link_1(Plink head){ int count1=0,count2=0; Plink p1=head, p2=head; while(p1){ /* p2每次都从头开始走 */ count2 = 0; p2=head; while(p2 && (p1 != p2)){ p2 = p2->next; count2++; } if((p1 == p2) && (count1 != count2)){ return p2; } p1=p1->next; count1++; } return NULL;}/* * 使用p1、p2两个指针，p1每次向前走一步，p2每次向前走两步， * 若在某个时候p1 == p2，则存在环. * 然后p1继续向前走，p2重头开始一步一步向前走，当p1 == p2时， * 那么该点就是入环时首个节点的地址 */Plink check_link_2(Plink head){ int flag=0; Plink p1=head, p2=head; while(p2){ p1=p1->next; if(p2->next){ p2=p2->next->next; } if(p1 == p2){ flag=1; break; } } if(flag){ p2=head; while( p1!=p2 ){ p1=p1->next; p2=p2->next; } return p1; } return NULL;}/* 删除链表 */void delete_link(Plink *head){ return;}int main{ int i=0,n=0; int ret=0; Plink root=NULL; Plink node=NULL; /* 创建一个单链表 */ for(i=1; i<=LINK_MAX; i++){ create_link(&root, i); } /* 在单链表中设定一个环，让尾节点指向链表中的第n个节点 */ n = 5; ret = create_loop(&root,n); if(ret){ printf(“no\\n”); }else{ printf(“yes\\n”); } /* 打印链表 */ n = 20; print_link(root,n); /* 检查该环 */ node = check_link_1(root); if(node == NULL){ printf(“单链表中不存在环\\n”); }else{ printf(“单链表中存在环,进入环节点的首地址:%x, data:%d\\n”,node, node->data); } /* 删除链表 */ delete_link(&root); return 0;}篇2：笔试实例：判断单链表中是否存在环
笔试实例：判断单链表中是否存在环
#include “stdafx.h”
typedef char eleType; // 定义链表中的数据类型
typedef struct listnode { // 定义单链表结构
eleType data;
struct listnode *next;
}node;
node *create(int n) { // 创建单链表，n为节点个数
node *p = (node *)malloc(sizeof(node));
node *head = p; head->data = ‘A’;
for(int i=’B'; i<’A'+n; i++) {
p = (p->next = (node *)malloc(sizeof(node)));
p->data = i;
p->next = NULL;
}
return head;
}
void addCircle(node *head, int n) { // 增加环，将链尾指向链中第n个节点
node *q, *p = head;
for(int i=1; p->next; i++) {
if(i==n) q = p;
p = p->next;
}
p->next = q;
}
int isCircle(node *head) { // 这是笔试时需要写的最主要函数，其他函数可以不写
node *p=head,*q=head;
while( p->next && q->next) {
p = p->next;
if (NULL == (q=q->next->next)) return 0;
if (p == q) return 1;
}
return 0;
}
int main(int argc, char* argv[]) {
node *head = create(12);
addCircle(head, 8); // 注释掉此行，连表就没有环了
printf(“%d\\n”, isCircle(head));
}
判断单链表中是否有环，计算出环的首地址 C语言实现.doc
将本文的Word文档下载到电脑，方便收藏和打印
