// 面试题22：链表中倒数第k个结点

// 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，

// 本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，

// 从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是

// 值为4的结点。

//O（n）的解法：维护两个指针，让A走B前头，前K步，A到头，B就是解了，但是这个问题在于程序鲁棒性

#include <iostream>

#include "List.h"

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)//注意无符号K

{

    if (pListHead == nullptr || k == )//鲁棒检查一：头结点和K不能为0

        return nullptr;

    ListNode *pAhead = pListHead;

    ListNode *pBehind = pListHead;

    for (unsigned int i = ; i < k - ; ++i)

    {

        if (pAhead->m_pNext != nullptr)//鲁棒检测二：得有K个节点

            pAhead = pAhead->m_pNext;

        else

        {

            return nullptr;

        }

    }

    while (pAhead->m_pNext != nullptr)

    {

        pAhead = pAhead->m_pNext;

        pBehind = pBehind->m_pNext;

    }

    return pBehind;

}

// ====================测试代码====================

// 测试要找的结点在链表中间

void Test1()

{

    printf("=====Test1 starts:=====\n");

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    printf("expected result: 4.\n");

    ListNode* pNode = FindKthToTail(pNode1, );

    PrintListNode(pNode);

    DestroyList(pNode1);

}

// 测试要找的结点是链表的尾结点

void Test2()

{

    printf("=====Test2 starts:=====\n");

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    printf("expected result: 5.\n");

    ListNode* pNode = FindKthToTail(pNode1, );

    PrintListNode(pNode);

    DestroyList(pNode1);

}

// 测试要找的结点是链表的头结点

void Test3()

{

    printf("=====Test3 starts:=====\n");

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    printf("expected result: 1.\n");

    ListNode* pNode = FindKthToTail(pNode1, );

    PrintListNode(pNode);

    DestroyList(pNode1);

}

// 测试空链表

void Test4()

{

    printf("=====Test4 starts:=====\n");

    printf("expected result: nullptr.\n");

    ListNode* pNode = FindKthToTail(nullptr, );

    PrintListNode(pNode);

}

// 测试输入的第二个参数大于链表的结点总数

void Test5()

{

    printf("=====Test5 starts:=====\n");

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    printf("expected result: nullptr.\n");

    ListNode* pNode = FindKthToTail(pNode1, );

    PrintListNode(pNode);

    DestroyList(pNode1);

}

// 测试输入的第二个参数为0

void Test6()

{

    printf("=====Test6 starts:=====\n");

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    printf("expected result: nullptr.\n");

    ListNode* pNode = FindKthToTail(pNode1, );

    PrintListNode(pNode);

    DestroyList(pNode1);

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    system("pause");

    return ;

}