文章目录
- 剑指 Offer 22. 链表倒数第K节点：
- 样例 1：
- 分析
- 题解
-
- rust
- go
- typescript
- python
- c
- c
- java
- 原题传送门：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
剑指 Offer 22. 链表倒数第K节点：
输入链表，输出链表中倒数第K节点。为了满足大多数人的习惯，这个问题从1开始计数，即链表的尾节点是倒数第一节点。
例如，链表有 6 从头节点开始，它们的值依次是 1、2、3、4、5、6。链表倒数第 3 节点值为 4 的节点。
样例 1：
给定一个链表： 1->2->3->4->5, 和 k = 2. 返回链表 4->5. 分析
- 面对这个算法题目，二当家陷入沉思。
- 这个问题并不难做到。首先，你可以通过第一次得到链表的长度，你可以知道目标节点是第二个节点，第二次得到目标节点。
- 也可以一次遍历，比如用一个数组，一边遍历一边把节点拉平到数组，遍历结束后就知道节点下标了。
- 也可以使用常数级别的额外空间。使用快指针和慢指针，让快指针提前通过K个节点，然后让快指针继续通过，直到快指针到链表的末端，慢指针是目标节点。
题解
rust
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode {
// pub val: i32, // pub next: Option<Box<ListNode>> // } // // impl ListNode {
// #[inline] // fn new(val: i32) -> Self {
// ListNode {
// next: None, // val // } // } // } impl Solution {
pub fn get_kth_from_end(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
let mut ans = head; let mut fast = ans.clone(); for _ in 0..k {
fast = fast.unwrap().next; } while fast.is_some() {
fast = fast.unwrap().next;
ans = ans.unwrap().next;
}
ans
}
}
go
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func getKthFromEnd(head *ListNode, k int) *ListNode {
ans := head
fast := head
for k > 0 {
fast = fast.Next
k--
}
for fast != nil {
fast = fast.Next
ans = ans.Next
}
return ans
}
typescript
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function getKthFromEnd(head: ListNode | null, k: number): ListNode | null {
let ans = head;
let fast = head;
while (--k >= 0) {
fast = fast.next;
}
while (fast) {
fast = fast.next;
ans = ans.next;
}
return ans;
};
python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
ans = head
fast = head
for _ in range(k):
fast = fast.next
while fast:
fast = fast.next
ans = ans.next
return ans
c
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
struct ListNode *ans = head;
struct ListNode *fast = head;
while (--k >= 0) {
fast = fast->next;
}
while (fast) {
fast = fast->next;
ans = ans->next;
}
return ans;
}
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) {
ListNode *ans = head;
ListNode *fast = head;
while (--k >= 0) {
fast = fast->next;
}
while (fast) {
fast = fast->next;
ans = ans->next;
}
return ans;
}
};
java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode ans = head;
ListNode fast = head;
while (--k >= 0) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
ans = ans.next;
}
return ans;
}
}
原题传送门：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
非常感谢你阅读本文~ 欢迎【点赞】【收藏】【评论】~ 放弃不难，但坚持一定很酷~ 希望我们大家都能每天进步一点点~ 本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~