编程猫官方网站/网络营销推广公司名称

一、题目描述

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

二、输入描述

一个链表

三、输出描述

链表的倒数第k个结点

四、牛客网提供的框架

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

五、解题思路

建两个结点指针，一个指针为起始节点，另外一个位距离起始节点长度为k的末尾节点。从原链表的头开始不断向后寻找，当末尾节点找到最后时，起始节点所只想的是倒数第k个节点。

寻找过程如下图：

六、代码

/*
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(k <= 0) return NULL;ListNode *goalNode, *kNode;goalNode = pListHead;kNode = goalNode;for(int i = 1; i < k; i++){if(kNode) kNode = kNode->next;if(!kNode) return NULL;}while(kNode && kNode->next){kNode = kNode->next;goalNode = goalNode->next;}return goalNode;}
};