算法（一）求链表中的倒数第K 个结点

ゝ一世哀愁。 2022-08-09 06:45 173阅读 0赞

**在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。**  
输入可能包含多个测试样例，输入以EOF结束。  
对于每个测试案例，输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000)：n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素。  
输入的第二行包括n个数t(1<=t<=1000000)：代表链表中的元素。

**采用两个指针，第一个指针提前k-1步向下走，第二个指针再随着第一个指针一直走。知道第一个指针指向末尾，第二个指针的元素的值，便是我们所要求得的值。**

p1 = link->next;
        for(i=1;i<k;i++){
            p1 = p1->next;
        }
        p2 = link->next;
        while(p1->next!=NULL){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2->number;

但是考虑到特殊情况：

1 如果输入的k是0，也就是说是个非法的值。解决办法

2 如果链表为空，根本找不到要查找的值。解决办法

if(link->next == NULL || k == 0)
            return -1;

3 如果p1已经到了链表的末尾，而p2还没有开始，也就是说，链表的长度根本不够k个，怎么办呢？解决办法

p1 = link->next;
    for(i=1;i<k;i++){
        if(p1->next == NULL)
            return -1;
        p1 = p1->next;
    }

include <stdio.h>
    include <stdlib.h>
    typedef struct node{
        int number;
        struct node * next;
    }Node;
    int getK(Node *link,int k);
    int main(){
        int n,k,i,temp;
        int flag;
        while(scanf("%d %d",&n,&k)!=EOF && n>=0 && n<=1000 && k>=0 && k<=1000 ){
            Node *link = (Node *)malloc(sizeof(Node));
            link->next = NULL;
             flag = 0;
             Node *tail;
             tail = link;
            for(i=0;i<n;i++){
                scanf("%d",&temp);
                Node *n = (Node *)malloc(sizeof(Node));
                n->next = tail->next;
                tail->next = n;
                tail = tail->next;
                n->number = temp;
            }
            int numberK = getK(link,k);
            numberK ==-1?printf("NULL\n"):printf("%d\n",numberK);
        }
        return 0;
    }
    int getK(Node *link,int k){
        Node *p1,*p2;
        int i;
        if(link->next == NULL || k == 0)
            return -1;
        p1 = link->next;
        for(i=1;i<k;i++){
            if(p1->next == NULL)
                return -1;
            p1 = p1->next;
        }
        p2 = link->next;
        while(p1->next!=NULL){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2->number;
    }