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

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

算法:

#include<iostream>
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 = "<<e;
    return 0;
}
/**
*    寻找倒数第index个元素，找到则将该元素的值赋给e，否则直接返回.
*    1<=index<=list.size()
*
**/
void search(List list,int index,ElemType &e)
{
    if(!list || index<0 || index>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<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

寻找单链表中倒数第k个元素,布布扣,bubuko.com

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

原文：http://blog.csdn.net/chdjj/article/details/22109691