寻找单链表中倒数第k个元素

原理：设置快慢指针，快指针和慢指针初始时都指向链表首节点，然后快指针向后走k个单位，再让满指针和快指针同时向后走，当慢指针的值为空时快指针指向的节点的数据域即为所求。

算法:

#include
  
   
using namespace std;

typedef int ElemType;
typedef struct _NODE_//节点声明,头结点数据域存放链表长度
{
    ElemType data;
    struct _NODE_ *next;
}Node,*pNode,*List;

void search(List,int,int&);//寻找倒数第k个元素
void printList(List);
int main()
{
    int size;
    cin>>size;
    ElemType data;
    List list = (pNode)malloc(sizeof(Node));
    if(!list)
    {
        return -1;
    }
    list->data = 0;
    list->next = NULL;

    for(int i = 0; i < size;i++)
    {
        cin>>data;
        pNode pNew = (pNode)malloc(sizeof(Node));
        if(!pNew)
        {
            return -1;
        }
        pNew->next = list->next;
        pNew->data = data;
        list->next = pNew;
        list->data++;
    }
    cout<<"print list:";
    printList(list);
    int index,e;
    cin>>index;
    search(list,index,e);
    cout<<"e = "<
   
    list->data)//参数判断 return; pNode p,q;//设置快慢指针 p = q = list->next; while(index-->0) { /*if(!q) { return; }*/ q = q->next; } while(q) { p = p->next; q = q->next; } e = p->data; } void printList(List list) { if(!list) { return; } pNode p = list->next; while(p) { cout<
    
     data<<" "; p = p->next; } cout<
     
      测试：