题解 | # 输出单向链表中倒数第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

输出：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;
    }

	
}

复杂度分析