算法训练篇（4）

1.判断一个链表是否存在环，例如下面这个链表就存在一个环：例如N1->N2->N3->N4->N5->N2就是一个有环的链表

c语言版：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct link{
 5     int data;
 6     struct link *next;
 7 };
 8 
 9 int isLoop(struct link* head){
10     struct link* p1,*p2;
11     if(head == NULL || head->next == NULL)
12         return 0;
13     p1 = head;
14     p2 = head;
15     do{
16         p1 = p1->next;
17         p2 = p2->next->next;
18     }while(p1 != NULL && p2 != NULL && p1 != p2);
19     if(p1 == p2)
20         return 1;
21     else
22         return 0;
23 
24 }
25 
26 int main()
27 {
28     
29 }

View Code

2.单向链表的反转

c语言版：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct link{
 5     int data;
 6     struct link *next;
 7 };
 8 
 9 void reserve(struct link* head){
10     if(head == NULL || head->next == NULL)
11         return;
12     struct link * pre,*nex,*p;
13     pre = head;
14     p = head->next;
15     nex = head->next->next;
16     do{
17         p->next = pre;
18         pre->next = NULL;
19         pre = p;
20         p = nex;
21         nex = nex->next;
22     }while(nex != NULL);
23     head = p;
24 
25 }
26 
27 int main()
28 {
29 
30 }

c语言（递归法）：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct link{
 5     int data;
 6     struct link *next;
 7 };
 8 //递归法
 9 struct link* reserve(struct link* p,struct link* head){
10     if(p == NULL || p->next == NULL){
11         head = p;
12     }
13     else{
14         struct link* temp = reserve(p->next,head);
15         temp->next = p;
16         return p;
17     }
18 }
19 
20 int main()
21 {
22 
23 }