Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2585290
  • 博文数量: 877
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 5920
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-05 12:25
个人简介

技术的乐趣在于分享,欢迎多多交流,多多沟通。

文章分类

全部博文(877)

文章存档

2021年(2)

2016年(20)

2015年(471)

2014年(358)

2013年(26)

分类: 敏捷开发

2014-07-23 16:19:27

http://blog.csdn.net/lxgwm2008/article/details/8907930
一、头文件

  1. #ifndef LISTUTILS_H  
  2. #define LISTUTILS_H  
  3.   
  4. typedef int ElemType;  
  5.   
  6. typedef struct _node  
  7. {  
  8.     ElemType data;  
  9.     struct _node *next;  
  10. } Node;  
  11.   
  12. /* 
  13. Description: get the intersection point of two list 
  14. Param:       headA: header of list1 
  15.              headB: header of list2 
  16. Return:      the intersection point or null for none 
  17. */  
  18. const Node *GetIntersectionPoint(const Node *headA, const Node *headB);  
  19.   
  20. /* 
  21. Description: reverse the given list 
  22. Param:       head: header of list 
  23. Return:      none 
  24. */  
  25. void ReverseList(Node *head);  
  26.   
  27. /* 
  28. Description: get the circle point of list 
  29. Param:       head: header of list 
  30. Return:      the circle point or null for none 
  31. */  
  32. const Node *GetCirclePoint(const Node *head);  
  33.   
  34. void PrintList(Node *head);  
  35. #endif // LISTUTILS_H  

二、C文件


  1. #include   
  2. #include "ListUtils.h"  
  3.   
  4. const Node *GetIntersectionPoint(const Node *headA, const Node *headB)  
  5. {  
  6.     const Node *tmpA, *tmpB;  
  7.     unsigned int lenA = 0, lenB = 0, i;  
  8.   
  9.     if(NULL == headA || NULL == headB || NULL == headA->next || NULL == headB->next){  
  10.         return NULL;  
  11.     }  
  12.   
  13.     tmpA = headA;  
  14.     //make tmpA points to the end of headA  
  15.     while(NULL != tmpA->next){  
  16.         tmpA = tmpA->next;  
  17.         ++lenA;  
  18.     }  
  19.   
  20.     tmpB = headB;  
  21.     //make tmpB points to the end of headB  
  22.     while(NULL != tmpB->next){  
  23.         tmpB = tmpB->next;  
  24.         ++lenB;  
  25.     }  
  26.   
  27.     //no intersection point  
  28.     if(tmpA != tmpB){  
  29.         return NULL;  
  30.     }  
  31.   
  32.     tmpA = headA->next;  
  33.     tmpB = headB->next;  
  34.     if(lenA > lenB){  
  35.         for(i = 0; i < lenA - lenB; ++i){  
  36.             tmpA = tmpA->next;  
  37.         }  
  38.     }else if(lenB > lenA){  
  39.         for(i = 0; i < lenB - lenA; ++i){  
  40.             tmpB = tmpB->next;  
  41.         }  
  42.     }  
  43.   
  44.     while(tmpA != tmpB){  
  45.         tmpA = tmpA->next;  
  46.         tmpB = tmpB->next;  
  47.     }  
  48.   
  49.     return tmpA;  
  50. }  
  51.   
  52. const Node *GetCirclePoint(const Node *head)  
  53. {  
  54.     Node *fast = NULL;  
  55.     Node *slow = NULL;  
  56.     Node *circlePoint  = NULL;  
  57.   
  58.     //empty list  
  59.     if(NULL == head || NULL == head->next){  
  60.         return NULL;  
  61.     }  
  62.   
  63.     fast = slow = head->next;  
  64.     while(fast && fast->next){  
  65.         fast = fast->next->next;  
  66.         slow = slow->next;  
  67.         if(fast == slow){  
  68.             circlePoint = fast;  
  69.             break;  
  70.         }  
  71.     }  
  72.   
  73.     //no circlePoint  
  74.     if(NULL == circlePoint){  
  75.         return NULL;  
  76.     }  
  77.   
  78.     fast = head->next;  
  79.     while(fast != slow){  
  80.         fast = fast->next;  
  81.         slow = slow->next;  
  82.     }  
  83.   
  84.     return fast;  
  85. }  
  86.   
  87. void ReverseList(Node *head)  
  88. {  
  89.     Node *first, *second, *third;  
  90.   
  91.     //if there is less than one node, return  
  92.     if(NULL == head || NULL == head->next){  
  93.         return;  
  94.     }  
  95.   
  96.     first = head->next;  
  97.     second = first->next;  
  98.     first->next = NULL;  
  99.     while(second){  
  100.         //cache the next node of "second"  
  101.         third = second->next;  
  102.         //insert the "second" node to the front of result list  
  103.         second->next = first;  
  104.         //move the first node to point to "second"  
  105.         first = second;  
  106.         //restore the "second" node  
  107.         second = third;  
  108.     }  
  109.   
  110.     head->next = first;  
  111.   
  112.     return;  
  113. }  
  114.   
  115. void PrintList(Node *head)  
  116. {  
  117.     Node *node;  
  118.     int pos = -1;  
  119.     if(NULL == head)  
  120.     {  
  121.         return;  
  122.     }  
  123.     node = head->next;  
  124.     while(node)  
  125.     {  
  126.         printf("[%d]----[%d]\n", ++pos, node->data);  
  127.         node = node->next;  
  128.     }  
  129. }  
阅读(505) | 评论(0) | 转发(0) |
0

上一篇:memcpy源码

下一篇:Qt工程加入对 C99 支持

给主人留下些什么吧!~~