问题描述
已知一个带有头结点的单链表,在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第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");
}