阜阳网站建设价格低,专注网站建设16年,asp.net 建立网站吗,自己做的网站主页打开速度剑指 Offer 22. 链表中倒数第k个节点
难度#xff1a;easy\color{Green}{easy}easy 题目描述
输入一个链表#xff0c;输出该链表中倒数第k个节点。为了符合大多数人的习惯#xff0c;本题从1开始计数#xff0c;即链表的尾节点是倒数第1个节点。
例如#xff0c;一个链…剑指 Offer 22. 链表中倒数第k个节点
难度easy\color{Green}{easy}easy 题目描述
输入一个链表输出该链表中倒数第k个节点。为了符合大多数人的习惯本题从1开始计数即链表的尾节点是倒数第1个节点。
例如一个链表有 666 个节点从头节点开始它们的值依次是 1、2、3、4、5、61、2、3、4、5、61、2、3、4、5、6。这个链表的倒数第 333 个节点是值为 444 的节点。
示例
给定一个链表: 1-2-3-4-5, 和 k 2.返回链表 4-5.算法
(直接遍历)
最简单直接的方法即为顺序查找假设当前链表的长度为 n则我们知道链表的倒数第 k 个节点即为正数第 n−k 个节点此时我们只需要顺序遍历到链表的第 n−k 个节点即为倒数第 k 个节点。
我们首先求出链表的长度 n然后顺序遍历到链表的第 n−k 个节点返回即可。
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是链表的长度。最坏需要遍历链表两次。 空间复杂度 : O(1)O(1)O(1)
C 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {int n 0;for (auto p head; p; p p-next) n ;auto dummy new ListNode(-1);dummy-next head;for (int i 0; i n - k 1; i ) {dummy dummy-next;}return dummy;}
};
