面试题22. 链表中倒数第k个节点

题目描述:

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

思路:

1、这道题首先能够想到的就是,先从头走到链表的尾部,再回溯k步,但是本题的链表是单向链表,单向链表只有从头向后的指针,没有从后往前的指针,因此我们并没有办法回溯。
2、既然不能从后往前回溯,那么我们还是考虑从头往后遍历。如果链表有n个节点,那么倒数第k个节点,就是从头往后数第n-k+1个节点。如果我们能得到链表的长度,那么我们就需要从头向后走n-k+1步即可。如何获取链表的长度n呢?就需要我们从头向后遍历,并累计结点的个数。然后再从头向后走n-k+1。可以看出我们需要遍历2次链表。第一次计算链表的长度。第二次为了找到倒数第k个节点;
3、如何能够只遍历一次就能找到倒数第k个节点呢? 我们定义2个指针,都指向头结点。第一个指针从头结点先遍历向后走k-1,第二个指针保持不动。从第k步开始,p1走,p2也跟着走。两个指针始终保持k-1的距离,直到p1走到链表的尾节点时,p2刚好走到倒数第k个节点。

Java解法(双指针):

class Solution {
    public int[] printNumbers(int n) {
        int maxNum = (int)Math.pow(10, n) - 1;
        int[] ans = new int[maxNum];
        for(int i = 1; i <= maxNum; i++)
        {
            ans[i-1] = i;
        }
        return ans;
    }
}

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容