UDN-企业互联网技术人气社区

板块导航

浏览  : 781
回复  : 1

[资源] web前端开发面试题及答案②

[复制链接]
cat77的头像 楼主
发表于 2016-9-7 10:18:24 | 显示全部楼层 |阅读模式
本帖最后由 cat77 于 2016-9-7 10:20 编辑

  找到⼀个未知长度单链表的倒数第K个节点

  题目:

  找到⼀个未知长度单链表的倒数第K个节点

  提示:

  head—>1—>2—>3—>4—>5—>6—>7—>8—>9—>10—>NULL.其中倒数第0个节点是NULL,倒数第1个节点是10,倒数第10个节点是1.
1.jpg

  如上图可以看出,遍历pPcur的同时将pos--,直到pos等于0时将pPre++,最后发现pCur最后指向空时,pPre指向的位置就是反向pos的位置。
  1. //  
  2. //  找到⼀个未知长度单链表的倒数第K个节点.c  
  3. //  c++  
  4. //  
  5. //  Created by 刘龙玲   
  6. //  Copyright © 2016年 liulongling. All rights reserved.  
  7. //  
  8.   
  9. #include <stdio.h>  
  10.   
  11. typedef struct Node  
  12. {  
  13.     int num;  
  14.     struct Node* next;  
  15. }Node;  
  16.   
  17. Node* listNodeCreat()  
  18. {  
  19.     Node* head = NULL;  
  20.     head =  (Node*)malloc(sizeof(Node*));  
  21.     if(head == NULL)  
  22.     {  
  23.         return NULL;  
  24.     }  
  25.       
  26.     head->num = -1;  
  27.     head->next = NULL;  
  28.       
  29.     Node* pCur = head;  
  30.     Node* pNew = NULL;  
  31.       
  32.     for(int i = 1;i < 11;i++)  
  33.     {  
  34.         pNew = (Node*)malloc(sizeof(Node*));  
  35.         if(pNew == NULL)  
  36.         {  
  37.             break;  
  38.         }  
  39.          
  40.         pNew->num = i;  
  41.         pNew->next=NULL;  
  42.          
  43.         pCur->next = pNew;  
  44.         pNew->next=NULL;  
  45.         pCur = pNew;  
  46.     }  
  47.       
  48.     return head;  
  49. }  
  50.   
  51. Node* findNodeByK(Node* head,int pos)  
  52. {  
  53.     Node *pPre = NULL;  
  54.     Node *pCur = NULL;  
  55.       
  56.     if(head == NULL || pos<=0)  
  57.     {  
  58.         return NULL;  
  59.     }  
  60.       
  61.     pPre = head;  
  62.     pCur = head;  
  63.       
  64.     while(pos > 0)  
  65.     {  
  66.         pCur = pCur ->next;  
  67.         pos--;  
  68.         if(pCur == NULL)  
  69.         {  
  70.             return NULL;  
  71.         }  
  72.     }  
  73.     while(pCur!=NULL)//上图红色区域表示该代码执行的地方  
  74.     {  
  75.         pCur = pCur->next;  
  76.         pPre = pPre->next;  
  77.     }  
  78.     return pPre;  
  79. }  
  80.   
  81. int main()  
  82. {  
  83.     Node* head  =listNodeCreat();  
  84.     for(int i = 0;i < 11;i++)  
  85.     {  
  86.         Node* node = findNodeByK(head, i);  
  87.         if(node!=NULL)  
  88.         {  
  89.             printf("i= %d num= %d\n",i,node->num);  
  90.         }else{  
  91.             printf("没有找到%d node\n",i);  
  92.         }  
  93.     }  
  94.       
  95.     return 0;  
  96. }
复制代码

相关帖子

发表于 2016-9-7 10:55:07 | 显示全部楼层
赞一个
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部