Chinaunix首页 | 论坛 | 博客
  • 博客访问: 244918
  • 博文数量: 63
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 750
  • 用 户 组: 普通用户
  • 注册时间: 2015-05-10 21:59
  • 认证徽章:
个人简介

付出,终有回报!

文章分类

全部博文(63)

文章存档

2018年(6)

2017年(24)

2016年(6)

2015年(27)

分类: C/C++

2015-05-20 23:29:49

     链表这种常见的基础数据结构,不仅在Linux内核中大量使用,在互联网公司的许多业务中也大量使用。那么,参加IT笔试、面试的,这些方面的知识绝对不会少。各方搜罗打听,整理一下这些常见的操作,以备后用。
    这个是
link.h

点击(此处)折叠或打开

  1. #ifndef _LINK_H_
  2. #define _LINK_H_

  3. #define TRUE 1
  4. #define FALSE 0

  5. //链表的控制信息
  6. typedef struct Link
  7. {
  8.     struct LinkNode *head; //指向链表的头节点
  9.     int count; //链表中的元素个数
  10. }Link;

  11. //链表节点的结构体
  12. typedef struct LinkNode
  13. {
  14.     int data; //数据域
  15.     struct LinkNode * next; //指针域
  16. }LinkNode;


  17. typedef unsigned char Boolean;

  18. Link *init_link(void) ; //链表的初始化
  19. void destroy_link(Link **link); //链表的销毁
  20. void push_front(Link *link, int value); //头部插入
  21. void push_back(Link *link, int value); //尾部插入
  22. Boolean pop_front(Link *link); //头部删除
  23. Boolean pop_back(Link *link); //尾部删除
  24. void show_link(Link *link); //显示链表的信息
  25. void sort_link_ascend(Link *link); //升序排列单链表
  26. void sort_link_descend(Link *link); //降序排列单链表
  27. Link *merger_two_links(Link *link1, Link *link2);
  28. //普通归并两个有序单链表
  29. Link *merger_two_links_recure(Link *link1, Link *link2);
  30. //递归地归并两个有序的单链表
  31. Link *copy_link(Link *link); //单链表的拷贝
  32. int get_link_count(Link *link); //得到链表的节点数目
  33. LinkNode *find_mid_node(Link *link); //找到链表的中间节点
  34. LinkNode *find_reciprocal_node(Link *link, int num); //找到链表的倒数第n个节点
  35. Link *reverse_link(Link *link); //反转链表
  36. void recur_reverse_print_link(Link *link); //逆序打印链表
  37. Boolean has_circle(Link *link); //判断链表是否有环
  38. Boolean is_link_intersect(Link *link1, Link *link2);
  39. //判断两个链表是否有交点
  40. LinkNode *get_first_common_node(Link *link1, Link *link2);
  41. //找到两个相交链表的第一个交点
  42. void delete_one_node(Link *link, LinkNode *node);
  43. //在O(1)时间复杂度删除链表节点
  44. LinkNode *get_first_node_in_circle(Link *link);
  45. //得到环内的第一个节点

  46. #endif


  1. #include "link.h"

  2. Link *init_link(void) //链表初始化
  3. {
  4.     Link *link = (Link *)malloc(sizeof(Link));
  5.     if(link == NULL){
  6.         fprintf(stderr, "the memory is full!\n");
  7.         exit(1);
  8.     }
  9.     bzero(link, sizeof(Link));
  10.     link->head = buy_node(); //为链表购买头节点
  11.     return link;
  12. }

  13. void destroy_link(Link **link) //链表的销毁
  14. {
  15.     LinkNode *p_node = NULL;

  16.     if(link == NULL || (*link) == NULL){ //如果链表不存在,直接退出
  17.         return ;
  18.     }

  19.     p_node = (*link)->head;
  20.     while(p_node != NULL){ //循环地删除链表的节点
  21.         (*link)->head = (*link)->head->next;
  22.         free(p_node);
  23.         p_node = (*link)->head;
  24.     }
  25.     free(*link); //删除链表的控制信息节点
  26.     *link = NULL; //为了安全起见,将链表的控制信息指针指向NULL
  27. }

  28. void push_back(Link *link, int value) //尾部插入
  29. {
  30.     LinkNode *p_node = NULL;
  31.     LinkNode *q_node = NULL;

  32.     if(link == NULL || link->head == NULL){ //判断链表的控制信息和链表是否存在
  33.         return ;
  34.     }

  35.     p_node = link->head; //指向链表的点
  36.     while(p_node->next != NULL){ //找到最后一个节点
  37.         p_node = p_node->next;
  38.     }
  39.     // 找到最后一个节点的位置,购买一个新的节点,
  40.     // 赋予设定值,并且添加到链表的末尾
  41.     q_node = buy_node();
  42.     q_node->data = value ;
  43.     p_node->next = q_node ;
  44.     (link->length)++ ; //链表长度增加1
  45. }

  46. void push_front(Link *link, int value) //头部插入
  47. {
  48.     LinkNode *p_node = NULL;

  49.     if(link == NULL || link->head == NULL){ //判断链表的控制信息和链表是否存在
  50.         return ;
  51.     }
  52.     
  53.     p_node = buy_node() ; //购买新的节点并赋初值
  54.     p_node->data = value ;
  55.     p_node->next = link->head->next;
  56.     link->head->next = p_node ; //将新生成的节点添加到链表的第一个节点
  57.     (link->length)++ ;
  58. }

  59. Boolean pop_back(Link *link) //尾部删除结点
  60. {
  61.     Boolean ok = FALSE;
  62.     LinkNode *p_node = NULL;
  63.     LinkNode *q_node = NULL;
  64.  
  65.     if(link == NULL || link->length == ZERO){ //如果链表不存在或者没有节点,返回尾部删除失败
  66.         return ok;
  67.     }
  68.     if(link->length == ONLY_ONE){ //如果只有一个链表节点,直接删除
  69.         free(link->head->next);
  70.         link->head->next = NULL;
  71.     }else{ //找到最后一个节点
  72.         for(p_node = link->head->next; p_node->next != NULL;
  73.             p_node = p_node->next){
  74.             q_node = p_node; //记录下最后一个节点的上一个节点位置
  75.         }
  76.         free(p_node);
  77.         q_node->next = NULL;
  78.     }
  79.     (link->length)--;
  80.     return ok = TRUE;
  81. }

  82. Boolean pop_front(Link *link) //头部删除结点
  83. {
  84.     Boolean ok = FALSE;
  85.     LinkNode *p_node = NULL;

  86.     if(link == NULL || link->length == ZERO){ //如果链表不存在直接返回删除失败
  87.         return ok;
  88.     }
  89.     p_node = link->head->next;
  90.     link->head->next = p_node->next;
  91.     free(p_node);
  92.     (link->length)--;
  93.     return ok = TRUE;
  94. }

  95. static void swap_link_node(LinkNode *node1, LinkNode *node2) //交换两个链表的节点信息
  96. {
  97.     LinkNode temp = *node1;
  98.     *node1 = *node2;
  99.     *node2 = temp;
  100. }

  101. //交换两个链表节点的next值
  102. static void swap_link_pointer(LinkNode **pointer1, LinkNode **pointer2)
  103. {
  104.     LinkNode *temp = *pointer1;
  105.     *pointer1 = *pointer2;
  106.     *pointer2 = temp;
  107. }

  108. void sort_link_ascend(Link *link) //单链表的升序排列
  109. {
  110.     LinkNode *p_node = NULL; //冒泡排序中的i
  111.     LinkNode *q_node = NULL; //冒泡排序中的j
  112.     LinkNode temp = {0}; //链表节点的中间变量
  113.     LinkNode *p_temp = NULL; //链表节点指针的中间变量
  114.       
  115.     //当链表不存在或者只有一个节点时,不需要进行排序
  116.     if(link == NULL || link->head == NULL || link->length == ONLY_ONE){
  117.         return ;
  118.     }
  119.     
  120.     for(p_node = link->head->next; p_node != NULL; p_node = p_node->next){
  121.         for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
  122.             //模仿冒泡排序进行
  123.             if(p_node->data > q_node->data){
  124.                 swap_link_node(p_node, q_node); //交换两个链表的节点信息
  125.                 swap_link_pointer(&(p_node->next), &(q_node->next)); //交换两个链表节点的next值
  126.             }
  127.         }
  128.     }
  129. }

  130. void sort_link_descend(Link *link) //单链表的降序排列
  131. {
  132.     LinkNode *p_node = NULL; //冒泡排序中的i
  133.     LinkNode *q_node = NULL; //冒泡排序中的j
  134.     LinkNode temp = {0}; //链表节点的中间变量
  135.     LinkNode *p_temp = NULL; //链表节点指针的中间变量
  136.       
  137.     //当链表不存在或者只有一个节点时,不需要进行排序
  138.     if(link == NULL || link->head == NULL || link->length == ONLY_ONE){
  139.         return ;
  140.     }
  141.     
  142.     for(p_node = link->head->next; p_node != NULL; p_node = p_node->next){
  143.         for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
  144.             //模仿冒泡排序进行
  145.             if(p_node->data < q_node->data){
  146.                 swap_link_node(p_node, q_node); //交换两个链表的节点信息
  147.                 swap_link_pointer(&(p_node->next), &(q_node->next)); //交换两个链表节点的next值
  148.             }
  149.         }
  150.     }
  151. }

  152. void show_link(Link *link) //显示链表信息
  153. {
  154.     LinkNode *p_node = NULL;

  155.     if(link == NULL || link->head == NULL){ //判断链表控制信息和链表头节点是否存在
  156.         return ;
  157.     }
  158.     printf("show link messages:\n");
  159.     for(p_node = link->head->next; p_node != NULL;
  160.         p_node = p_node->next){ //从头到尾依次遍历每个链表节点
  161.         printf("%d ", p_node->data);
  162.     }
  163.     printf("\n");
  164. }

  165. Link *merger_two_links_recure(Link *link1, Link *link2) //递归的合并两个链表
  166. {
  167.     Link *result = NULL;
  168.     if(link1 == NULL || link2 == NULL
  169.      || (link1->length == ZERO && link2->length == ZERO)){
  170.         return result;
  171.     }
  172.     

  173.     result = init_link(); //初始化链表
  174.     result->head->next = merger_links(link1->head->next, link2->head->next);
  175.     result->length = link1->length + link2->length;
  176.     return result;
  177. }

  178. static LinkNode *merger_links(LinkNode *link1_first, LinkNode *link2_first) //进行链表的递归合并
  179. {
  180.     LinkNode *result = NULL;
  181.     
  182.     if(link1_first == NULL){ //本链表为空,返回另外一个链表
  183.         return copy_link_by_node(result, link2_first);
  184.     }else if(link2_first == NULL){
  185.         return copy_link_by_node(result, link1_first);
  186.     }
  187.    
  188.     if(link1_first->data < link2_first->data){
  189.         result = buy_node();
  190.         result->data = link1_first->data;
  191.         result->next = merger_links(link1_first->next, link2_first);
  192.     }else{
  193.         result = buy_node();
  194.         result->data = link2_first->data;
  195.         result->next = merger_links(link1_first, link2_first->next);
  196.     }
  197.     return result;
  198. }

  199. static LinkNode *copy_link_by_node(LinkNode *des_link, LinkNode *src_link) //通过节点来拷贝链表
  200. {
  201.     LinkNode *result = NULL;
  202.     LinkNode *p_node = NULL;

  203.     if(src_link == NULL){ //如果源链表不存在直接返回
  204.         return NULL;
  205.     }
  206.     
  207.     //否则进行拷贝
  208.     des_link = buy_node();
  209.     result = p_node = des_link ;
  210.     des_link->data = src_link->data;
  211.     src_link = src_link->next;
  212.     while(src_link != NULL){
  213.         des_link = buy_node() ;
  214.         des_link->data = src_link->data;
  215.         p_node->next = des_link ;
  216.         p_node = des_link ;
  217.         src_link = src_link->next;
  218.     }
  219.     
  220.     return result;
  221. }

  222. Link *copy_link(Link *src_link) //通过控制信息来拷贝链表
  223. {
  224.     Link *des_link = NULL;
  225.     LinkNode *p_node = NULL;

  226.     if(src_link == NULL){ //源链表不存在,无需进行拷贝
  227.         return NULL;
  228.     }

  229.     des_link = init_link(); //初始化链表
  230.     p_node = src_link->head->next;
  231.    
  232.     while(p_node != NULL){
  233.         push_back(des_link, p_node->data);
  234.         p_node = p_node->next;
  235.     }
  236.     
  237.     return des_link;
  238. }

  239. Link *merger_two_links(Link *link1, Link *link2) //合并两个有序链表
  240. {
  241.     Link *result = NULL;
  242.     LinkNode *link1_move = NULL;
  243.     LinkNode *link2_move = NULL;

  244.     //如果两个链表不存在或者没有元素的话,则不进行合并
  245.     if(link1 == NULL || link2 == NULL ||
  246.         link1->length == ZERO || link2->length == ZERO){
  247.             return NULL;
  248.     }
  249.     
  250.     //对链表进行排序
  251.     sort_link_ascend(link1);
  252.     sort_link_ascend(link2);
  253.   
  254.     //show_link(link1);
  255.     //show_link(link2);

  256.     result = init_link(); //初始化结果链表
  257.     //合并两个链表
  258.     //
  259.     //1.首先让各个链表都指向初始化位置
  260.     link1_move = link1->head->next;
  261.     link2_move = link2->head->next;

  262.     while(link1_move != NULL && link2_move != NULL){
  263.         //如果link1链表当前节点的元素值大与link2,则把link1的节点元素值尾插到result末尾
  264.         if(link1_move->data < link2_move->data){
  265.             push_back(result, link1_move->data);
  266.             link1_move = link1_move->next;
  267.         }else{
  268.             push_back(result, link2_move->data);
  269.             link2_move = link2_move->next;
  270.         }
  271.     }

  272.     //当两个链表中有任意一个遍历完毕,把另外一个链表追加到result末尾
  273.     if(link1_move == NULL){
  274.         while(link2_move != NULL){
  275.             push_back(result, link2_move->data);
  276.             link2_move = link2_move->next ;
  277.         }
  278.     }
  279.     if(link2_move == NULL){
  280.         while(link1_move != NULL){
  281.             push_back(result, link1_move->data);
  282.             link1_move = link1_move->next ;
  283.         }
  284.     }
  285.     return result;
  286. }

  287. static LinkNode *buy_node(void) //购买链表结点
  288. {
  289.     LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
  290.     if(node == NULL){
  291.         fprintf(stderr, "the memory is full!\n");
  292.         exit(1);
  293.     }
  294.     bzero(node, sizeof(LinkNode));
  295.     return node;
  296. }

  297. int get_link_length1(Link *link) //求链表长度
  298. {
  299.     int count = 0;
  300.     LinkNode *p_node = NULL;

  301.     if(link == NULL || link->head == NULL){ //如果链表不存在,直接返回负值
  302.         return -1;
  303.     }
  304.   
  305.     p_node = link->head->next; //让p_node指向链表的第一个节点
  306.     while(p_node != NULL){
  307.         count++;
  308.         p_node = p_node->next;
  309.     }
  310.  
  311.     return count;
  312. }

  313. int get_link_length2(Link *link) //求链表长度
  314. {
  315.     if(link == NULL){
  316.         return -1;
  317.     }
  318.     return link->length;
  319. }

  320. Link *reverse_link_nonrecure(Link *link) //翻转链表
  321. {
  322.     LinkNode *p_node = NULL;
  323.     LinkNode *q_node = NULL;
  324.     LinkNode *head = NULL;
  325.   
  326.     //如果链表不存在或者链表元素为0或者链表元素为1,则不进行反转
  327.     if(link == NULL || link->length == ZERO
  328.      ||link->length == ONLY_ONE){
  329.         return link;
  330.     }
  331.     
  332.     p_node = head = link->head->next; //指向第一个节点
  333.     head = head->next ; //指向第二个节点
  334.     q_node = head->next ; //指向第三个节点

  335.     if(q_node == NULL){ //如果只有两个节点
  336.         head->next = p_node;
  337.         p_node->next = NULL;
  338.     }else{ //如果是三个或三个以上节点
  339.         p_node->next = NULL ;
  340.         do{
  341.             head->next = p_node ;
  342.             p_node = head ;
  343.             head = q_node ;
  344.             q_node = q_node->next;
  345.         }while(q_node != NULL);
  346.         head->next = p_node ;
  347.     }
  348.   
  349.     link->head->next = head;
  350.     return link;
  351. }

  352. LinkNode *find_reciprocal_node1(Link *link, int num) //查找链表的倒数第k个节点(简便)
  353. {
  354.     int move_count = 0 ;
  355.     LinkNode *p_node = NULL;
  356.     //如果链表不存在或者是空链表,或者倒数的数字大于链表的长度,则直接返回NULL
  357.     if(link == NULL || link->length == ZERO
  358.     || num > (link->length) || num <= 0){
  359.         return NULL;
  360.     }
  361.     move_count = link->length - num; //总数-倒数的个数==移动的节点数
  362.     p_node = link->head->next ;
  363.     
  364.     while(move_count > 0){
  365.         p_node = p_node->next;
  366.         move_count--;
  367.     }
  368.    
  369.     return p_node;
  370. }

  371. LinkNode *find_reciprocal_node2(Link *link, int num) //查找链表的倒数第k个节点
  372. {
  373.     LinkNode *prev_node = NULL;
  374.     LinkNode *next_node = NULL;
  375.     int i = 0;
  376.     
  377.     if(link == NULL || link->length == ZERO || num <= 0){
  378.         return NULL;
  379.     }
  380.     
  381.     //先遍历和后遍历的指针都指向初始位置
  382.     prev_node = link->head->next;
  383.     next_node = link->head->next;

  384.     for(i = 0; i < num - 1; ++i){
  385.         if(prev_node->next != NULL){
  386.             printf("prev:%d %ld\n", prev_node->data, prev_node);
  387.             prev_node = prev_node->next;
  388.         }else{
  389.             return NULL;
  390.         }
  391.     }

  392.     //让先前的节点先走k步,再让后续节点从头遍历,当先前的
  393.     //节点到达末尾时,后续的节点就是指向了倒数第k个
  394.     while(prev_node->next == NULL){
  395.         prev_node = prev_node->next;
  396.         next_node = next_node->next;
  397.     }

  398.     printf("next:%d %ld\n", next_node->data, next_node);
  399.     return next_node;
  400. }

  401. LinkNode *find_mid_node1(Link *link) //查找链表中间结点
  402. {
  403.     LinkNode *p_node = NULL;
  404.     LinkNode *q_node = NULL;

  405.     if(link == NULL || link == ZERO){
  406.         return NULL;
  407.     }

  408.     p_node = link->head->next;
  409.     q_node = link->head->next;
  410.    
  411.     while(p_node->next != NULL){
  412.         p_node = p_node->next;
  413.         q_node = q_node->next;
  414.         if(p_node->next != NULL){
  415.             p_node = p_node->next;
  416.         }
  417.     }

  418.     return q_node;
  419. }

  420. LinkNode *find_mid_node2(Link *link) //查找链表中间节点
  421. {
  422.     LinkNode *p_node = NULL;
  423.     int move_count = 0 ;

  424.     if(link == NULL || link == ZERO){
  425.         return NULL;
  426.     }

  427.     if(link->length == ONLY_ONE){ //如果只有一个节点,则返回该节点
  428.         return link->head->next;
  429.     }

  430.     move_count = (link->length) / 2 - 1; //找到中间节点需要移动的步数
  431.     p_node = link->head->next;
  432.     while(move_count >= 0){
  433.        p_node = p_node->next;
  434.        move_count--;
  435.     }
  436.     return p_node;
  437. }

  438. void recur_reverse_print_link(Link *link) //递归逆序打印链表
  439. {
  440.     if(link == NULL || link->length == ZERO){ //如果链表不存在或者没有元素,不进行打印
  441.         return ;
  442.     }
  443.     printf("reverse link message:\n");
  444.     rever_print_link(link->head->next);
  445.     printf("\n");
  446. }

  447. static void rever_print_link(LinkNode *link_first) //递归进行打印
  448. {
  449.     if(link_first == NULL){
  450.         return ;
  451.     }else{
  452.         rever_print_link(link_first->next);
  453.         printf("%d ", link_first->data);
  454.     }
  455. }

  456. void nonrecur_reverse_print_link(Link *head) //非递归逆序打印链表
  457. {
  458.     /*使用栈来存储链表的元素,再反向打印*/
  459. }

  460. Boolean has_circle(Link *link) //判断链表是否有环
  461. {
  462.     Boolean ok = FALSE;
  463.     LinkNode *p_node = NULL;
  464.     LinkNode *q_node = NULL;
  465.   
  466.     if(link == NULL || link->length < 2){ //如果链表不存在或者少于两个节点,则不存在环
  467.         return ok;
  468.     }

  469.     p_node = link->head->next;
  470.     q_node = link->head->next;

  471.     while((p_node != NULL) && (p_node->next != NULL)){ //快速移动的指针和它下一个节点都不为空
  472.          p_node = p_node->next->next;
  473.          q_node = q_node->next;

  474.          //如果快速节点和较慢节点相遇,说明它们是在环中相遇的
  475.          if(p_node == q_node){
  476.              return ok = TRUE;
  477.          }
  478.     }
  479.         
  480.     return ok;
  481. }

  482. Boolean is_link_intersect(Link *link1, Link *link2) //判断两个链表是否有交点
  483. {
  484. /*
  485.  * 如果两个链表有交点,那么他们的最后一个节点一定相同。
  486.  *
  487.  * */
  488.     Boolean ok = FALSE;
  489.     LinkNode *p_node = NULL;
  490.     LinkNode *q_node = NULL;
  491.  
  492.     if(link1 == NULL || link2 == NULL
  493.     || link1->length == ZERO || link2->length == ZERO){
  494.     //如果两个链表不存在,或者说没有元素的话,直接返回无交点
  495.         return ok;
  496.     }
  497.     
  498.     p_node = link1->head->next;
  499.     q_node = link2->head->next;
  500.   
  501.     //两个指针各自移动到所属链表的末尾
  502.     while(p_node->next != NULL){
  503.         p_node = p_node->next;
  504.     }

  505.     while(q_node->next != NULL){
  506.         q_node = q_node->next;
  507.     }
  508.     
  509.     if(p_node == q_node){ //判断末尾指针是否相等
  510.         ok = TRUE;
  511.     }
  512.    
  513.     return ok;
  514. }

  515. LinkNode *get_fisrt_common_node(Link *link1, Link *link2) //找到链表的第一个交点
  516. {
  517.     int l1_len = 0;
  518.     int l2_len = 0;
  519.     int dis_len = 0;
  520.     LinkNode *p_node = NULL;
  521.     LinkNode *q_node = NULL;
  522.     //首先判断链表是否有交点,如果没有直接返回NULL
  523.     if(!is_link_intersect(link1, link2)){
  524.         return NULL;
  525.     }
  526.    
  527.     p_node = link1->head->next;
  528.     q_node = link2->head->next;
  529.     
  530.     //判断两个链表的长度和差值
  531.     l1_len = link1->length;
  532.     l2_len = link2->length;

  533.     if(l1_len > l2_len){ //如果link1长,则先让它移动l1_len-l2_len步
  534.         dis_len = l1_len - l2_len;
  535.         while(dis_len--){
  536.             p_node = p_node->next;
  537.         }
  538.     }else{
  539.         dis_len = l2_len - l1_len;
  540.         while(dis_len--){
  541.             q_node = q_node->next;
  542.         }
  543.     }

  544.     while(p_node != q_node){ //如果两个指针相等,该节点为交点
  545.         p_node = p_node->next;
  546.         q_node = q_node->next;
  547.     }
  548.    
  549.     return p_node;
  550. }

  551. LinkNode *get_first_node_in_circle(Link *link) //找到有环单链表中的第一个节点
  552. {
  553.     //先判断是否有环,有的话记录下相交的节点
  554.     LinkNode *p_node = NULL;
  555.     LinkNode *q_node = NULL;
  556.     LinkNode *p_tail = NULL;

  557.     if(link == NULL || link->length < 2){
  558.         return NULL;
  559.     }

  560.     p_node = link->head->next;
  561.     q_node = link->head->next;

  562.     while((p_node != NULL) && (p_node->next != NULL)){
  563.         p_node = p_node->next->next;
  564.         q_node = q_node->next;
  565.         if(p_node == q_node){
  566.             break ;
  567.         }
  568.     }

  569.     if(p_node == NULL || p_node->next == NULL){
  570.         return NULL;
  571.     }
  572.     
  573.     // 将环中的此节点作为假设的相交的尾节点,将问题转化成求两个链表
  574.     // 相交的第一个节点的问题。
  575.     p_tail = q_node; //记录此节点为末尾节点
  576.     LinkNode *p_head1 = link->head->next;
  577.     LinkNode *p_head2 = p_tail->next;
  578.    
  579.     //分别记录两个链表到p_tail的长度
  580.     int len1 = 1;
  581.     p_node = p_head1;
  582.     while(p_node != p_tail){
  583.         p_node = p_node->next;
  584.         len1++;
  585.     }
  586.    
  587.     int len2 = 1;
  588.     q_node = p_head2;
  589.     while(q_node != p_tail){
  590.         q_node = q_node->next;
  591.         len2++;
  592.     }
  593.     
  594.     p_node = p_head1;
  595.     q_node = p_head2;
  596.    
  597.     if(len1 > len2){
  598.         int dis = len1 - len2;
  599.         while(dis--){
  600.             p_node = p_node->next;
  601.         }
  602.     }else{
  603.         int dis = len2 - len1;
  604.         while(dis--){
  605.             q_node = q_node->next;
  606.         }
  607.     }
  608.    
  609.     while(p_node != q_node){
  610.         p_node = p_node->next;
  611.         q_node = q_node->next;
  612.     }
  613.     
  614.     return p_node;
  615. }

  616. void delete_one_node(Link *link, LinkNode *be_deleted) //O(1)时间复杂度删除链表节点
  617. {
  618.      LinkNode *temp = NULL;
  619.      //如果链表不存在或者被删除的节点不存在,直接退出
  620.      if(link == NULL || be_deleted == NULL || link->length == ZERO){
  621.          return ;
  622.      }
  623.      
  624.      if(be_deleted->next != NULL){ //如果被删除节点不是末尾节点
  625.          //先将下一个结点的数据进行复制,然后删除下一个节点
  626.          be_deleted->data = be_deleted->next->data;
  627.          temp = be_deleted->next;
  628.          be_deleted->next = temp->next;
  629.          free(temp);
  630.      }else{ //如果是末尾节点
  631.          pop_back(link);
  632.      }
  633. }

  634. void show_link_length(Link *link) //显示链表的长度
  635. {
  636.     if(link == NULL){ //如果链表不存在直接退出
  637.         return ;
  638.     }
  639.     printf("the link length is:%d\n", link->length);
  640. }

阅读(1293) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册