【轻知识】反转链表、快慢指针检查环
惭愧，翻开旧博客，三年多前看郝斌视频，写过一次链表（那个视频倒是没讲反转链表）。现在，好好学算法把。少年。
#include
#includetypedef struct Node {
int data;
struct Node* pNext;
} NODE,*PNODE;
PNODE create_list();
void traverse_list(PNODE);
PNODE reverse_list(PNODE);
int check_circle(PNODE pHead);
PNODE create_circle_list();
int main() {
PNODE pHead = create_list();
traverse_list(pHead);
pHead = reverse_list(pHead);
printf("--------\n");
printf("%d", pHead->pNext->data);
printf("%d", pHead->pNext->pNext->data);
traverse_list(pHead);
PNODE circle_list= create_circle_list();
int is_circle = check_circle(circle_list);
printf("is_circle=%d\n", is_circle);
}
PNODE create_list() {
//1.首先mallc 一个地址
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (pHead == NULL) {
printf("malloc error");
}
int len;
printf("please input len:");
scanf("%d", &len);
printf("len=%d\n", len);
PNODE tempNode = pHead;
int i;
for(i = 0;
i < len;
i++) {
//分配节点
PNODE newNode = (PNODE)malloc(sizeof(NODE));
if (newNode == NULL) {
printf("malloc error");
}
printf("please input value:");
int val;
scanf("%d", &val);
newNode->data = https://www.it610.com/article/val;
newNode->pNext = NULL;
tempNode->pNext = newNode;
tempNode = newNode;
}
return pHead;
}
void traverse_list(PNODE pHead) {
PNODE t = pHead->pNext;
while(t != NULL) {
printf("data=https://www.it610.com/article/%d/n", t->data);
t = t->pNext;
}
return ;
}
PNODE reverse_list(PNODE pHead) {
PNODE t = pHead->pNext;
PNODE reverse = NULL;
PNODE tempNode = NULL;
while(t != NULL) {
tempNode = t->pNext;
if (reverse == NULL) {
reverse = t;
reverse->pNext = NULL;
} else {
t->pNext = reverse;
reverse = t;
}
t = tempNode;
}
pHead->pNext = reverse;
return pHead;
}
PNODE create_circle_list() {
//1.首先mallc 一个地址
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (pHead == NULL) {
printf("malloc error");
}
int len;
printf("please input len:");
scanf("%d", &len);
printf("len=%d\n", len);
PNODE tempNode = pHead;
int i;
PNODE circleNode = NULL;
for(i = 0;
i < len;
i++) {
//分配节点
PNODE newNode = (PNODE)malloc(sizeof(NODE));
if (newNode == NULL) {
printf("malloc error");
}
printf("please input value:");
int val;
scanf("%d", &val);
newNode->data = https://www.it610.com/article/val;
newNode->pNext = NULL;
tempNode->pNext = newNode;
tempNode = newNode;
if (circleNode == NULL && i == 2) {
circleNode = newNode;
}
if (len == i+1) {
newNode->pNext = circleNode;
}
}
return pHead;
}
int check_circle(PNODE pHead) {
PNODE t = pHead->pNext;
PNODE t1 = t;
while(t != NULL && t1 !=NULL) {
if (t->data =https://www.it610.com/article/= t1->data) {
return 1;
//表示有环的存在
}
printf("%d",t->data);
t = t->pNext;
t1 = t1->pNext->pNext;
}
return 0;
}
参考资料：
【【轻知识】反转链表、快慢指针检查环】《鏈表》http://yanshinian.com/lianbiao
