T11 - 링크 의 마지막 k 번 째 노드

제목 설명
링크 를 입력 하여 이 링크 의 마지막 k 번 째 노드 를 출력 합 니 다.
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 32M, 기타 언어 64M
문제 풀이 의 사고 방향.
이 문 제 는 스 택 을 도입 하여 링크 를 옮 겨 다 니 고 한 번 에 스 택 에 넣 은 다음 에 스 택 에서 k 개의 노드 를 꺼 내 는 것 이 바로 원 하 는 것 입 니 다.그러나 이렇게 해서 링크 만 옮 겨 다 녔 지만 스 택 을 도입 하여 추가 적 인 공간 소 모 를 가 져 왔 기 때문에 가장 좋 은 알고리즘 은 아니다.
그러면 생각 을 바 꾸 고 마지막 k 번 째 노드 를 구하 지만 링크 는 처음부터 끝까지 옮 겨 다 닐 수 밖 에 없다.따라서 만약 에 우리 가 링크 의 길 이 를 알 수 있다 면 우 리 는 처음부터 뒤로 제 length - k + 1 개의 노드 를 옮 겨 다 닐 수 있다.이 방법 은 두 순환 이 고 모든 순환 시간의 복잡 도 는 o (n) 이다.
좀 더 분석 하면 링크 만 한 번 옮 겨 다 닐 수 있 습 니까?한 번 만 옮 겨 다 니 려 면 포인터 가 제 length - k + 1 노드 를 가리 키 는 곳 까지 옮 겨 다 녀 야 하지만 length 를 모 르 면 length 를 바 꿀 수 있 는 방법 을 고려 해 야 합 니 다.한 바늘 로 처음부터 끝까지 옮 겨 다 니 면 length 에 해당 한 다 는 생각 이 듭 니 다. 한 바늘 더 주세요.
소스 코드

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* fir = NULL;
        ListNode* las = NULL;
        fir = pListHead;
        las = pListHead;
        //  k 
        int a=k;
        //       
        int count=0;
        //fir     ，       ；
        // fir      k    ，las          ，
        //  ， fir      ，las        k   
        while(fir!=NULL){
            fir = fir -> next;
            count++;
            if(a<1){
                las = las->next;
            }
            a--;
        }
        if(count<k) return NULL;
        return las;
    }
};