알고리즘 (1) 링크 의 마지막 K 번 째 노드 를 구하 십시오.

2 차원 배열 에서 모든 줄 은 왼쪽 에서 오른쪽으로 증가 하 는 순서에 따라 정렬 되 고 모든 열 은 위 에서 아래로 증가 하 는 순서에 따라 정렬 된다.함 수 를 완성 하 십시오. 이러한 2 차원 배열 과 정 수 를 입력 하여 배열 에 이 정수 가 있 는 지 판단 하 십시오.입력 은 여러 개의 테스트 샘플 을 포함 할 수 있 으 며, 입력 은 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
"):printf("%d
",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;
}