每日算法题 | 剑指offer 链表专题 （5）链表中倒数第k个节点
2021-03-11 00:30
标签：注意 归类 和为s的两个数字 字符串 linked 第一个公共结点 好的 奇数 序列化 链表中倒数第k个节点 输入一个链表的头结点，从尾到头反过来打印出每个结点的值 为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。当时，从链表结点的定义可以看出本题中的链表是单向链表，单向链表的结点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通，它只适用于双向链表。 有没有只遍历一次链表的方法呢？本题其实是很典型的快慢双指针问题，快指针先走k步，然后快慢指针再同时往前走，当快指针走到尽头时，慢指针刚好在倒数第k个节点的位置上。这样只需要遍历一次链表即可。唯一需要注意的问题是小心参数k值大于链表长度。 注：面试季来了，不管是作为面试者还是以后作为面试官，了解算法这门程序员之间的沟通方式都是非常必要的。找过工作的朋友应该都听说过《剑指offer》，虽然书中只有六十多道题目，但是道道都是经典。 如果是单纯的面试需求，剑指offer的优先级肯定是在Leetcode之前，总的说它有三个优点： 它的缺点是： 剑指offer刷题交流群 扫码添加微信，一定要备注研究方向+地点+学校+昵称（如机器学习+上海+上交+汤姆） 每日算法题 | 剑指offer 链表专题 （5）链表中倒数第k个节点 标签：注意 归类 和为s的两个数字 字符串 linked 第一个公共结点 好的 奇数 序列化 原文地址：https://blog.51cto.com/15054042/2564449
题目
题目要求
解题思路
思路：看到本题我们很自然的一个想法是从尾结点往前倒退k步，但是对于单链表是行不通的。那我们换个思路，假设链表有n个结点，要求倒数第k个结点，其实也就是从前往后数第n-k+1个结点，这个思路只需要遍历两次链表即可。 
代码实现
Python :
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
pre = post = head
# 快指针先走k步
for i in range(k):
# 如果k大于链表长度，返回空
if pre == None:
return None
pre = pre.next
# 快慢指针同时往前走
while pre != None:
pre = pre.next
post = post.next
return postC++
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
// 查找倒数第0个节点和输入空指针
if(pListHead == NULL || k == 0){
return NULL;
}
// 两个指针遍历链表
ListNode *pAhead = pListHead;
ListNode *pBehind = pListHead;
// 第一个指针从链表的头结点走K-1步
for(unsigned int i = 0; i next != NULL){
pAhead = pAhead->next;
}
else{
return NULL;
}
}
// 第k个节点开始，两个指针同时遍历
while(pAhead->next != NULL){
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}
};JAVA
/**
* 输入一个链表，输出该链表中倒数第k哥结点。
* 为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。
* 例如一个链表有6个结点，从头结点开始它们的值依次是1，2，3，4，5，6.这个链表的倒数第3个结点是值为4的结点
*/
package swordForOffer;
import utils.ListNode;
public class E15KthNodeFromEnd {
public ListNode FindKthToTail(ListNode head,int k){
if(head == null || k 后记
算法题主要分成数据结构和具体算法部分，简单归类如下。基本每道题都很精彩，所以这里就不一一洗写了，题解可以看看我的代码仓库或者讨论区的内容。数据结构类题目
▲长按加群
文章标题：每日算法题 | 剑指offer 链表专题 （5）链表中倒数第k个节点
文章链接：http://soscw.com/index.php/essay/62970.html