山东省建设管理信息网站,山东新闻今天最新消息,网站数据展示,html5下载教程目录 题目地址#xff1a; 剑指offer原题#xff1a; 我们直接看题解吧#xff1a; 解题方法#xff1a; 难度分析#xff1a; 审题目事例提示#xff1a; 解题思路#xff08;双指针#xff08;快慢指针#xff09;#xff09;#xff1a; 代码实现#xff1a; 代…目录 题目地址 剑指offer原题 我们直接看题解吧 解题方法 难度分析 审题目事例提示 解题思路双指针快慢指针 代码实现 代码优化 代码实现方法1 题目地址 LCR 140. 训练计划 II - 力扣LeetCode 难度简单 今天刷链表中倒数第k个节点大家有兴趣可以点上看看题目要求试着做一下。
剑指offer原题 输入一个链表输出该链表中倒数第k个节点。 为了符合大多数人的习惯本题从1开始计数即链表的尾节点是倒数第1个节点。 例如一个链表有 6 个节点从头节点开始它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 我们直接看题解吧 解题方法 方法1、顺序查找需两次遍历先求出链表长度 方法2、双指针只需一次遍历不需要求出链表长度 两个方法的时间复杂度与时间复杂度均为n,1 难度分析 属于基础性题目链表基础以及双指针使用。 审题目事例提示 注意单链表的长度不包括头结点头节点看作位序0头结点指向的下一个节点为位序1。 解题思路双指针快慢指针 创建两个指针for,lat它们均指向头结点 for指针先走cnt步此时两个节点相差cnt个节点 for,lat指针同步往后移动最后直至fornull for 指针指向cnt1(实际为null),lat此时与for相差cnt 说白了就是不需要知道链表长度指针1先走k步然后指针2和指针1相差k同时前进当指针1指向链表最后一个元素的下一位即null时指针2即为所求。 代码实现
class Solution {public ListNode trainingPlan(ListNode head, int cnt) {ListNode former head, latter head; //创建双指针初始化指向头结点for(int i 0; i cnt; i) { //for先走cnt步if(former null) return null; //防止cnt大于链表长度直接返回null//因为此时没求解的意义了former former.next;}while(former ! null) { //同时往后移动直至for指针指向尾节点的下一位即nullformer former.next;latter latter.next;}return latter;}
}
代码优化
class Solution {public ListNode getKthFromEnd(ListNode head, int k) {ListNode slowhead,fasthead;int t 0; //加个变量t判断代替第一个for循环while(fast!null){if(tk) slowslow.next;fast fast.next;t;}return slow;}
}
代码实现方法1
class Solution {public ListNode trainningPlan(ListNode head, int cnt) {int n 0;ListNode node null;for (node head; node ! null; node node.next) {n;}for (node head; n cnt; n--) {node node.next;}return node;}
}
