/*

题目：

	链表中倒数第k个节点

*/

/*

思路：

	考虑边界条件：链表为空，k值超过链表长度。

	双指针：

		q指针指向第k个节点，p指针指向第1个节点。

		q指针指向最后一个节点，p指针指向倒数第k个节点。

*/

#include<iostream>

#include<string.h>

#include<algorithm>

#include<cmath>

#include<stdio.h>

using namespace std;

struct ListNode {

	int val;

	struct ListNode *next;

	ListNode(int x) :

			val(x), next(NULL) {

	}

};

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

    if(pListHead == nullptr || k == 0) return nullptr;

    ListNode* kNode = pListHead;

    ListNode* pNode = pListHead;

    for(int i = 1; pNode != nullptr && i < k; i++){

        pNode = pNode->next;

    }

    if(pNode == nullptr) return nullptr;

    while(pNode->next != nullptr){

        kNode = kNode->next;

        pNode = pNode->next;

    }

    return kNode;

}

int main(){

   ListNode* node1 = new ListNode(1);

   ListNode* node2 = new ListNode(2);

   ListNode* node3 = new ListNode(3);

   node1->next = node2;

   node2->next = node3;

   node3->next = nullptr;

   cout<<FindKthToTail(node1,4)->val<<endl;

}