链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

问题分析

可以使用两个指针，一个在表头，第二个先走k-1步。
然后同时查询链表，当第二个指针到达链表尾部时，第一个指针到达倒数第K个节点。

解题思路1

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

        if (pListHead == nullptr || k == 0)
        {
            return nullptr;
        }
        ListNode* firstList = pListHead;
        ListNode* secondList = pListHead;
        //第二个指针先走k-1步
        for (int i = 0; i < k-1; ++i)
        {
            if (secondList->next != nullptr)
            {
                secondList = secondList->next;
            }
            else
            {
                return nullptr;
            }
        }
        //同时走，直到第二个指针到达链表尾部,此时第一个指针就到达了
        while (secondList->next != nullptr)
        {
            firstList = firstList->next;
            secondList = secondList->next;
        }
        return firstList;

    }
};