单行链表寻找倒数第k个节点



单行链表寻找倒数第k个节点，

/**
*题目介绍：给出一个单向链表，输出该链表的倒数第k个节点
*           设尾节点开始从0编号
*/

解题思路：两个指针往后移动，一定要注意边界的处理情况。此处我设置了一个头指针，头指针不存数据，仅仅作为头标志。

 

 

[cpp] view plaincopy

  1. /**
  2. *题目介绍：给出一个单向链表，输出该链表的倒数第k个节点
  3. *           设尾节点开始从0编号
  4. */
  5. #include <iostream>
  6. #include <stdlib.h>
  7. #include <cstdio>
  8. using namespace std;
  10. struct node
  11. {
  12.     int value;
  13.     struct node * next;
  14. } *head;
  15. inline void nodeinit(struct node *n)
  16. {
  17.     n->next = NULL;
  18.     n->value = 0;
  19. }
  20. void creatnodelist()
  21. {
  22.     //头指针 应该首先分配地址
  23.     if(head == NULL)
  24.         head = (struct node *)malloc(sizeof(struct node));
  25.     nodeinit(head);
  26.     int v;
  27.     struct node * pt = head;
  28.     scanf(“%d”,&v);
  29.     while(v)
  30.     {
  31.         if(pt->next == NULL)
  32.             pt->next = (struct node *)malloc(sizeof(struct node));
  33.         pt=pt->next;
  34.         nodeinit(pt);
  35.         pt->value = v;
  36.         //cout<<pt->value ;
  37.         scanf(“%d”,&v);
  39.     }
  40. }
  41. int findLastK(int k)
  42. {
  43.     struct node * p1=head;
  44.     struct node * p2=head;
  45.     while(k–)
  46.         p1=p1->next;
  47.     p1=p1->next;
  48.     while(p1 != NULL)
  49.         p1=p1->next,p2=p2->next;
  50.     return p2->value;
  51. }
  52. void print()
  53. {
  54.     struct node * p=head->next;
  55.     while(p!=NULL)
  56.         cout<<p->value<<”  ”,p=p->next;
  57. }
  58. int main()
  59. {
  60.     cout << ”create node list:” << endl;
  61.     creatnodelist();
  62.     print();
  63.     int k;
  64.     cout<<”\ninput k :”;
  65.     scanf(“%d”,&k);
  66.     cout<<”\nthe last ”<<k<<” node is : ”<<findLastK(k)<<endl;
  68.     return 0;
  69. }