寻找链表中倒数第K个位置的元素(只能遍历一遍)

由于只能遍历一遍链表,我们无法先获取链表长度,在遍历到倒数第k个位置,这样的操作是遍历两次链表

用两个指针p、q其中p先走k步,然后q在和p同时走,当p到达结尾时,q正好在倒数第k个位置

实现代码

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

typedef int Elemtype;

typedef struct LNode
{
    Elemtype data;
    struct  LNode *next;
} LNode,*LinkList;




LinkList List_TailInsert(LinkList L)
{
    int x;
    L=(LinkList)malloc(sizeof(LinkList));//创建头节点
    L->next=NULL;

    LNode *r=L,*s;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*)malloc(sizeof(LNode*));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL; //使环化
    return L;
}



void PrintLinkList(LinkList L)
{
    printf("打印链表\n");
    LNode *r=L->next;
    while(r!=NULL)
    {
        printf("%d--->",r->data);
        r=r->next;
    }
    printf("\n");
}


int Search_k(LinkList L,int k)
{
    LNode *p=L->next,*q=L->next;
    int count=0;
    while(p!=NULL)
    {
        if(count<k)count++;//p提前移动
        else q=q->next;
        p=p->next;
    }
    if(count<k)return 0;
    else
    {
        printf("%d",q->data);
        return 1;
    }
}

int main()
{

    LinkList L;//头指针,创建链表
    printf("创建链表,输入链表的值 9999表示结束!\n");
    L=List_TailInsert(L);
    printf("需要查找倒数第几个位置:");
    int k;
    scanf("%d",&k);
    Search_k(L,k);

    return 0;
}