剑指Offer（十四）--链表中倒数第k个节点
- 题目描述
- 思路以及解析
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路以及解析
如果按照直观的做法，就是先走到链表的尾部，再回溯k步，这样就能找到这个节点，可问题是这个链表其实是单向链表。要回溯的话，就需要遍历两次。
第一次遍历的时候记录下链表的节点个数n，第二次遍历的时候应该遍历到第n-k-1个节点就可以啦。这样代码实现其实不难。
但是有没有更优的做法呢？
答案肯定是有的！！！
思路也比较清晰，那就是前后指针，先让第1个指针先走k步，然后第2个指针开始走，而且两个指针一起走，直到第一个指针走到最后的位置。当第一个指针走到最后的位置的时候，其实第二个指针停留的位置就是倒数第k个节点。
这种双指针的方式，其实还是蛮常见的，可以加深印象。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
ListNode first = head;
while (k != 0) {
if (first == null) {
return null;
}
first = first.next;
k--;
}
while (first!= null) {
head = head.next;
first = first.next;
}
return head;
}
}此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~
技术之路不在一时，山高水长，纵使缓慢，驰而不息。
- END -
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
