单链表倒数第K个节点的查找和显示

最近在学回顾之前学到的知识，正好碰到了关于链表查找的一道面试题，在此贴出来，与小伙伴们共同交流~

在刚看到题目，其实很容易就想到一个方法，就是先求链表的长度(length)，然后去超找第length-k+1个节点的值，再进行查找，先贴代码如下。

#include <stdio.h>
#include <malloc.h>
/*链表节点结构*/
typedef struct node{
    int data;
    struct node * pNext;
}NODE,*PNODE;
/*函数声明*/
PNODE create_list();
void show_list(PNODE p);
void show_list_list(PNODE p);
int serch_k(PNODE p,int k);
/*主函数*/
int main(){
    int k;
    int len;
    PNODE pHead=NULL;
    pHead=create_list();
    show_list(pHead);
    len=show_list_length(pHead);
    printf("\n%d",len);
    k=serch_k(pHead,2);//查找倒数第K个值
    printf("\n%d",k);
    return 0;
}
/*生产链表*/
PNODE create_list(void){
    int len;
    int val;
    int i;
    scanf("%d\n",&len);
    PNODE pHead=(PNODE)malloc(sizeof(NODE));
    if(pHead==NULL){
        printf("error");
    }
    PNODE pTail=pHead;
    pTail->pNext=NULL;
    for(i=0;i<len;i++){
        scanf("%d",&val);
        PNODE pNew=(PNODE)malloc(sizeof(NODE));
        if(pNew==NULL){
        printf("error");
        }
        pNew->data=val;
        pTail->pNext=pNew;
        pNew->pNext=NULL;
        pTail=pNew;
    }
    return pHead;
}
/*显示链表*/
void show_list(PNODE p){
    PNODE p1=p->pNext;
    if(p1==NULL){
        printf("error");
    }
    while(p1){
        printf("%d",p1->data);
        p1=p1->pNext;
    }
}
/*显示链表长度*/
int show_list_length(PNODE p){
    int count=0;
    PNODE p1=p->pNext;
    if(p1==NULL){
        printf("error");
    }
    while(p1){
        count++;
        p1=p1->pNext;
    }
    return count;
}
/*查找第k个节点的值*/
int serch_k(PNODE p,int k){
int i=0;
    PNODE p1=p; 
    int len=show_list_length(p);
    if(k>len){
        printf("error");
    }
    /*循环len-k+1次*/
    for(i=0;i<len-k+1;i++){
        p1=p1->pNext;
        
    }
    return p1->data;
}

这个算法需要对链表进行两次遍历，导致时间复杂度为O(N^2)，那有没有只需要一次遍历的呢，答案是有的。

首先先看下思路：p1和p2分别都是head指针，先将p2向右移动k次，如图2所示

图1

图2

这时候，只需要继续保持p1和p2等间距的右移，当p2的next为null，则证明p1所指的结点的值为倒数第k个节点的值

图3

这就是一次遍历找出倒数第k个节点的值，其时间复杂度为O(N)

具体代码如下所示

int serch_k(PNODE p,int k){
    int i;
    PNODE p1 = p;
        PNODE p2 = p;
    for (i = 0; i < k; i++) {
        p2 = p2->pNext;
    }
    while (p2 != NULL) {
        p1 = p1->pNext;
        p2 = p2->pNext;

    }
    return p1->data;
}

这是测试结果

图4

这就是单链表找倒数第k个结点的值的两种方法。

单链表倒数第K个节点的查找和显示

推荐阅读