Chinaunix首页 | 论坛 | 博客
  • 博客访问: 387030
  • 博文数量: 80
  • 博客积分: 1750
  • 博客等级: 上尉
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-13 11:35
文章分类
文章存档

2014年(3)

2013年(1)

2012年(54)

2011年(22)

分类: C/C++

2012-12-16 16:13:02

题目:
        已知带头节点的单链表,只有一个数据域和一个指针域。假设目前只给出了头指针list,在不改变链表的前提下,查找链表中倒数第K个位置的节点。若成功,则输出data域的值,并返回1,否则返回0.

算法思想:
        定义两个指针变量p和q,均指向头节点的下一个节点,p指针先移动,移动到K时,q指针跟着一起移动;当p移动到链表结尾时,q指针刚好移动到倒数第K个节点.

算法如下:
  1. typedef struct Node
  2. {
  3.      int data;
  4.      struct Node *link;
  5. } *LinkList;

  6. int searchK(LinkList list, int k)
  7. {
  8.       LinkList p, q;
  9.       int count = 0;
  10.       p = q = list -> link;

  11.       while(p != NULL){
  12.            if(count < k)
  13.                  count++;
  14.            else
  15.                  q = q -> next;
  16.            p = p -> next;
  17.       }
  18.  
  19.       if(count < k)
  20.            return 0;
  21.       else{
  22.            printf("%d ", q -> data);
  23.            return 1;
  24.       }
  25. }

  
阅读(991) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~