关于链表的几道题

evilknight

1. 
   
2. typedef struct Node
   
3. {
   
4.     int data ;
   
5.     node *next;
   
6. }node ;
   
7. typedef node * link ;
   
8. 
   
9. 表结点如上，现有一个带头结点的链表，
   
10. 要求写个程序，将表倒置
    
11. link reversse(link pHead)
    
12. {
    
13. // 在里面写
    
14. }
    
15. 
    
16. 现在有一个链表，写个程序，判断程序是否有环！
    
17. 伪代码也可！
    
18. 
    
19. 现在有二个链表，写个程序，判断他们是否相交!
    

复制代码

evilknight

1. 
   
2. typedef struct Node
   
3. {
   
4.     int data ;
   
5.     node *next;
   
6. }node ;
   
7. typedef node * link ;
   
8. 
   
9. 表结点如上，现有一个带头结点的链表，
   
10. 要求写个程序，将表倒置
    
11. link reversse(link pHead)
    
12. {
    
13.     link q, p , tmp;
    
14.     q = pHead->next ;
    
15.     p = q->next ;
    
16.    
    
17.     if (pHead == NULL)
    
18.     {
    
19.         return NULL ;
    
20.     }
    
21.    
    
22.     while (p != NULL)
    
23.     {
    
24.         tmp = p ;
    
25.         p = p->next ;
    
26.         tmp->next = q ;
    
27.         q = tmp;
    
28.     }
    
29.     return pHead = q ;
    
30. }
    
31. 
    
32. 现在有一个链表，写个程序，判断程序是否有环！
    
33. 伪代码也可！
    
34. 
    
35. int IsRing(link pHead)
    
36. {
    
37.     link q, p ;
    
38.    
    
39.     if (pHead == NULL)
    
40.     {
    
41.         return 0 ;
    
42.     }
    
43.    
    
44.     q = p = pHead->next ;
    
45.     for ( ;q != NULL && p != NULL && q != p; q = q->next, p = p->next->next)
    
46.     {
    
47.     }
    
48.    
    
49.     if (q == NULL || p == NULL)
    
50.     {
    
51.         return 0 ;
    
52.     }
    
53.     return 1 ;
    
54. }
    

复制代码

evilknight

1. 
   
2. 第三题如果只是单链表的话，可以试下将next的值保存起来！判断是否有相同的，有的话一定相交了！
   
3. 如果是循环链表的，记录二个pHead->next的值，看下走一次之后，是不是到了相同的地方！
   
4. 如果你们还有别的方法，可以说出来共享一下！
   

复制代码