第1章第2节练习题10 查找指定倒数结点

问题描述

已知一个带有头结点的单链表，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第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\n",p->data,k);
else
printf("It not find the number!\n");
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("\n");
}