问题描述

已知一个带有头结点的单链表，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点。若查找成功，算法输出该结点的data域的值

算法思想

倒数第k个位置，很容易想到的算法便是遍历整条单链表，得出单链表的长度len，然后再遍历(len−k)个结点便可以得到倒数第k个位置的结点的数据域。但是这样实际上就导致链表遍历了两次，时间复杂度为2×O(n)。
换个思路，使用两个指针p和q，让指针q先遍历k个结点，然后指针p和指针q同时开始遍历链表。当指针q指向表尾结点时，指针p所指的结点便是倒数第k个位置的结点。如此仅遍历一次便找到了倒数第k个位置上的结点。时间复杂度仅为O(n)。

算法描述

LNode* FindReK(LNode *head, int k)
{
    LNode *q=head->next;
    LNode *p=head->next;
    while(q){
        if(k){
            q=q->next;
            --k;
        }else{
            p=p->next;
            q=q->next;
        }
    }
    return p;
}

具体代码见附件。

附件

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

LinkList CreatList(LNode*);
LNode* FindReK(LNode*, int);
void Print(LNode*);

int main(int argc,char* argv[])
{
    LNode *head;
    head=(LNode*)malloc(sizeof(LNode));
    head=CreatList(head);
    Print(head);

    int k=3;
    LNode *p;
    p=FindReK(head,k);
    if(p)
        printf("The number is %d in the Reverse postion %dth
",p->data,k);
    else
        printf("It not find the number!
");
    return 0;
}
//头插法建立单链表
LinkList CreatList(LNode *head)
{
    LNode *L;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        L=(LNode*)malloc(sizeof(LNode));
        L->data=x;
        L->next=head->next;
        head->next=L;
        scanf("%d",&x);
    }
    return head;
}
//查找倒数第k个结点
LNode* FindReK(LNode *head, int k)
{
    LNode *q=head->next;
    LNode *p=head->next;
    while(q){
        if(k){
            q=q->next;
            --k;
        }else{
            p=p->next;
            q=q->next;
        }
    }
    return p;
}
//打印全部结点
void Print(LNode *head)
{
    LNode *p=head->next;
    while(p){
        printf("%4d",p->data);
        p=p->next;
    }
    printf("
");
}