题目描述

输入一个链表，输出该链表中倒数第k个结点。链表可能为空k可能等于0

思路

利用快慢指针写法，两个指针都指向头结点，一个指针先走k-1个节点，然后两个指针一起走，直到一个指针到达尾部。时间复杂度$O(n)$,一次遍历。

#include<bits/stdc++.h>
using namespace std;
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==NULL||k==0)return NULL;
        ListNode *findk=pListHead;
        while(k--){
            pListHead=pListHead->next;
            if(pListHead==NULL&&k==0)return findk;
            else if(pListHead==NULL) return NULL;
        }
        while(pListHead!=NULL){
            findk=findk->next;
            pListHead=pListHead->next;
        }
        return findk;
    }
};
int main(){
    Solution ac;
    ListNode head(1);
    ListNode *root=&head;
    for(int i=2;i<=10;++i){
        root->next=new ListNode(i);
        root=root->next;
    }
    root=&head;
    cout<<ac.FindKthToTail(root,10)->val<<endl;
    return 0;
}