链表有关
http://www.cnblogs.com/gw811/archive/2012/10/28/2743182.html
1、创建链表,倒置链表
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct node{ 5 int val; 6 struct node *next; 7 }Node; 8 9 //创建链表 10 Node *Creat(){ 11 int i,n,val; 12 Node *head,*p,*q; 13 head=NULL; 14 printf("val: "); 15 scanf("%d",&n); 16 17 for(i=0;i<n;i++){ 18 scanf("%d",&val); 19 p=(Node *)malloc(sizeof(Node)); 20 p->val=val; 21 if(head==NULL){ 22 head = p; 23 }else{ 24 q->next = p; 25 } 26 q = p; 27 } 28 p -> next = NULL; 29 return head; 30 } 31 32 //倒置链表 33 Node *Reverse(Node *head){ 34 Node *p,*q,*r; 35 p = head; 36 r = NULL; q = NULL; 37 38 while(p){ 39 q = p->next; 40 p->next = r; 41 r = p; 42 p = q; 43 } 44 return r; 45 } 46 47 //显示链表 48 void Show(Node *head){ 49 Node *p = head; 50 while(p){ 51 printf("%d",p->val); 52 p = p->next; 53 } 54 printf("\n"); 55 } 56 57 int main(){ 58 Node *h,*r; 59 h = Creat(); 60 Show(h); 61 r = Reverse(h); 62 Show(r); 63 }View Code
2、判断单链表是否有环
设置两个指针(fast,slow),初始值都指向头指针,slow每次前进一步,fast每次前进两步。
如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。
如果链表不存在环,fast先到达链表尾部。
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct node{ 5 int val; 6 struct node *next; 7 }Node; 8 9 //创建无环链表 10 Node *Creat(){ 11 int i,n,val; 12 Node *head,*p,*q; 13 head=NULL; 14 printf("val: "); 15 scanf("%d",&n); 16 17 for(i=0;i<n;i++){ 18 scanf("%d",&val); 19 p=(Node *)malloc(sizeof(Node)); 20 p->val=val; 21 if(head==NULL){ 22 head = p; 23 }else{ 24 q->next = p; 25 } 26 q = p; 27 } 28 p -> next = NULL; 29 return head; 30 } 31 32 //创建有环链表 33 Node *CreatRing(){ 34 int i,n,val; 35 Node *head,*p,*q; 36 head=NULL; 37 printf("val: "); 38 scanf("%d",&n); 39 40 for(i=0;i<n;i++){ 41 scanf("%d",&val); 42 p=(Node *)malloc(sizeof(Node)); 43 p->val=val; 44 if(head==NULL){ 45 head = p; 46 }else{ 47 q->next = p; 48 } 49 q = p; 50 } 51 p=(Node *)malloc(sizeof(Node)); 52 p->val=913; 53 q->next = p; 54 q = p; 55 q->next = head ->next; 56 return head; 57 } 58 59 //检测是否有环 60 int ifHasRing(Node *head){ 61 Node *fast=head,*slow=head; 62 while(fast && fast->next){ 63 fast = fast->next->next; 64 slow = slow->next; 65 if( fast == slow){ 66 break; 67 } 68 } 69 return fast && fast->next; 70 } 71 72 int main(){ 73 Node *h,*k; 74 h = Creat(); 75 if(ifHasRing(h)){ 76 printf("no1 : ring!!!\n"); 77 } 78 k = CreatRing(); 79 if(ifHasRing(k)){ 80 printf("no2 : ring!!!\n"); 81 } 82 }View Code
3、求有环单链表的环入口点
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct node{ 5 int val; 6 struct node *next; 7 }Node,*List; 8 9 //创建有环链表 10 Node *CreatRing(){ 11 int i,n,val; 12 Node *head,*p,*q; 13 head=NULL; 14 printf("val: "); 15 scanf("%d",&n); 16 17 for(i=0;i<n;i++){ 18 scanf("%d",&val); 19 p=(Node *)malloc(sizeof(Node)); 20 p->val=val; 21 if(head==NULL){ 22 head = p; 23 }else{ 24 q->next = p; 25 } 26 q = p; 27 } 28 p=(Node *)malloc(sizeof(Node)); 29 p->val=913; 30 q->next = p; 31 q = p; 32 q->next = head ->next; 33 return head; 34 } 35 36 //检测是否有环,并求环入口点 37 Node *ifHasRing(Node *head){ 38 Node *fast=head,*slow=head; 39 while(fast && fast->next){ 40 fast = fast->next->next; 41 slow = slow->next; 42 if( fast == slow){ 43 break; 44 } 45 } 46 if(fast==NULL||fast->next==NULL) 47 return NULL; 48 slow=head; 49 while(slow!=fast){ 50 slow=slow->next; 51 fast=fast->next; 52 } 53 return slow; 54 } 55 56 int main(){ 57 Node *k,*l; 58 k = CreatRing(); 59 l = ifHasRing(k); 60 printf("ring: %d\n",l->val); 61 62 }View Code 优质内容筛选与推荐>>