题解 | # 输出单向链表中倒数第k个结点#
输出单向链表中倒数第k个结点
http://www.nowcoder.com/practice/54404a78aec1435a81150f15f899417d
输出单向链表中倒数第k个结点
描述
输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
正常返回倒数第k个结点指针，异常返回空指针。
示例：
输入：
8
1 2 3 4 5 6 7 8
4
1 2 3 4 5 6 7 8
4
输出：5
方法一
思路分析
本题最直接的办法就是根据输入的数组直接输出倒数第k个数，不过本题题目要求使用单向链表，因此直接构造单向链表，然后顺序输出倒数第k个结点，输出时采用输出第n-k个结点。
核心代码
#include <bits/stdc++.h>
using namespace std;
struct Node{
int value;
struct Node* next;
Node(int value)
{
this->value=value;
}
};
int main(){
int count=0;
while(cin>>count)
{
Node *root = new Node(-1);
Node *p = root;
for (int i=0; i < count; ++i)//顺序构造链表
{
int num;
cin>>num;
Node *p = new Node(num);//下一个结点
p->next = NULL;
root->next = p;// 连接 当前节点 与 下一个结点
root = root->next;
}
root->next = NULL;//最后一个节点指向mull
int k=0;
cin>>k;
if(k<=0||k>count)
{
cout<<0<<endl;
continue;
}
for(int i=0;i<count-k+1;i++)//顺序找到第count-k个
{
p=p->next;
}
cout<<p->value<<endl;
}
}
复杂度分析
- 时间复杂度：时间花费在链表的构造和查找中，构造链表的时间复杂度为$O(n)$，查找的时间复杂度为$O(n)$，因此总的时间复杂度为$O(n)$
- 空间复杂度：构造链表需要的空间为正常使用，因此总的空间复杂度为$O(1)$
方法二
思路分析
根据方法一，我们可以设置一个数组存储输入的元素，然后根据数组元素从后往前构造链表，从而顺序输出链表第k个结点
核心代码
#include <bits/stdc++.h>
using namespace std;
struct Node{
int value;
struct Node* next;
Node(int value)
{
this->value=value;
}
};
vector<int>arr;
int main(){
int count=0;
while(cin>>count)
{
int index=count;
arr={};
while(index--)
{
int num;
cin>>num;
arr.push_back(num);
}
Node *root = new Node(-1);
Node *p = root;
for (int i=count-1;i>=0; i--)//按照数组倒序构造链表
{
Node *p = new Node(arr[i]);//下一个结点
p->next = NULL;
root->next = p;// 连接 当前节点 与 下一个结点
root = root->next;
}
root->next = NULL;//最后一个节点指向mull
int k=0;
cin>>k;
if(k<=0||k>count)
{
cout<<0<<endl;
continue;
}
for(int i=0;i<k;i++)//顺序找到第k个
{
p=p->next;
}
cout<<p->value<<endl;
}
}
复杂度分析
- 时间复杂度：时间花费在链表的构造和查找中，构造链表的时间复杂度为$O(n)$，查找的时间复杂度为$O(n)$，因此总的时间复杂度为$O(n)$
- 空间复杂度：需要额外设置一个数组存储输入的元素，因此总的空间复杂度为$O(max(n))$
方法三
思路分析
在构建链表时，可以通过首插法构造链表，然后顺序输出第k个结点
图解
核心代码
#include <bits/stdc++.h>
using namespace std;
struct Node{
int value;
struct Node* next;
Node(int value)
{
this->value=value;
}
};
vector<int>arr;
int main(){
int count=0;
while(cin>>count)
{
Node *root = new Node(-1);
root->next=NULL;
for (int i=0;i<count; i++)//按照首插法构造链表
{
int num=0;
cin>>num;
Node *p = new Node(num);//下一个结点
p->next = root;//插入到根节点之前
root= p;// 根节点向前移动一个位置
}
int k=0;
cin>>k;
if(k<=0||k>count)
{
cout<<0<<endl;
continue;
}
for(int i=0;i<k-1;i++)//从前往后顺序找到第k个
{
root=root->next;
}
cout<<root->value<<endl;
}
}
复杂度分析
- 时间复杂度：时间花费在链表的构造和查找中，构造链表的时间复杂度为$O(n)$，查找的时间复杂度为$O(n)$，因此总的时间复杂度为$O(nm)$
- 空间复杂度：除构造链表之外，不需要额外的存储空间，因此空间复杂度为$O(1)$
查看12道真题和解析
