题目
输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
思路一
因为是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们不能倒序遍历链表，只能正序遍历。假设整个链表有n个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点（从0开始计数）。我们只需要得到链表中结点的个数n，那我们只要从头结点开始往后走n-k-1步就可以了。
因此这种方法需要遍历链表两次。第一次得到链表中结点个数n，第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。时间复杂度为O(n)。
代码
/*------------------------------------
* 日期：2015-02-08
* 作者：SJF0115
* 题目: 9.链表中倒数第k个结点
* 来源：程序员面试题精选100题
---------------------------------------*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode* FindKthTailNode(ListNode* head,int k) {
if(head == nullptr || k < 0){
return nullptr;
}//if
// 统计链表个数
int count = 0;
ListNode *p = head;
while(p){
p = p->next;
++count;
}//while
// 不足K个
if(count < k){
return nullptr;
}//if
// 倒数第K个节点
int pos = count - k;
p = head;
for(int i = 0;i < pos;++i){
p = p->next;
}//for
return p;
}
};
int main(){
Solution s;
ListNode *head = new ListNode(1);
ListNode *node;
for(int i = 8;i >= 2;--i){
node = new ListNode(i);
node->next = head->next;
head->next = node;
}//for
ListNode *result = s.FindKthTailNode(head,3);
// 输出
if(result == nullptr){
cout<<"nullptr"<<endl;
}//if
else{
cout<<result->val<<endl;
}//else
return 0;
}
思路二
上面那种思路需要两次遍历，如何才能只需一次遍历呢？
如果我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动， k-1 步开始，第二个指针也开始从链表的头指针开始遍历，两个指针齐头并进。由于两个指针的距离保持在k-1；当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第
K个节点。
代码二
/*------------------------------------
* 日期：2015-02-08
* 作者：SJF0115
* 题目: 9.链表中倒数第k个结点
* 来源：程序员面试题精选100题
---------------------------------------*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode* FindKthTailNode(ListNode* head,int k) {
if(head == nullptr || k < 0){
return nullptr;
}//if
ListNode *p = head,*q = head;
// 指针p移动k-1步
int index = 1;
while(index < k && p != nullptr){
p = p->next;
++index;
}//while
// 不够K个
if(p == nullptr){
return nullptr;
}//if
// 同时移动
while(p->next){
p = p->next;
q = q->next;
}//while
return q;
}
};
int main(){
Solution s;
ListNode *head = new ListNode(1);
ListNode *node;
for(int i = 8;i >= 2;--i){
node = new ListNode(i);
node->next = head->next;
head->next = node;
}//for
ListNode *result = s.FindKthTailNode(head,8);
// 输出
if(result == nullptr){
cout<<"nullptr"<<endl;
}//if
else{
cout<<result->val<<endl;
}//else
return 0;
}
拓展
输入一个单向链表。如果该链表的结点数为奇数，输出中间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个节点。
代码
/*------------------------------------
* 日期：2015-02-08
* 作者：SJF0115
* 题目: 9.2链表中间结点
* 来源：程序员面试题精选100题
---------------------------------------*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode* FindMidNode(ListNode* head) {
if(head == nullptr){
return nullptr;
}//if
ListNode *slow = head,*fast = head;
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}//while
return slow;
}
};
int main(){
Solution s;
ListNode *head = new ListNode(1);
ListNode *node;
for(int i = 8;i >= 2;--i){
node = new ListNode(i);
node->next = head->next;
head->next = node;
}//for
ListNode *result = s.FindMidNode(head);
// 输出
if(result == nullptr){
cout<<"nullptr"<<endl;
}//if
else{
cout<<result->val<<endl;
}//else
return 0;
}
