面试题15. 链表中倒数第k个结点

本文主要是介绍面试题15. 链表中倒数第k个结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路：
Step1. 设置两个指针slow和fast，初始时均指向头结点
Step2. slow不动，fast向前走k-1步
Step3. 然后两个指针同时向前走，直到fast走到链表的结尾，此时slow指向的就是倒数第k个节点。

注意特殊输入：
输入空指针的情况
链表长度小于k的情况
k为0的情况

/*
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) {return head;}if(k == 0) {return null;}ListNode slow = head， fast = head;boolean overLength = false; //k是否超过长度while(--k != 0) {fast = fast.next;if(fast == null) {overLength = true;break;}}if(overLength) {return null;}while(fast.next!=null) {slow = slow.next;fast = fast.next;}return slow;}
}写法2：
/*
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) return null;ListNode p = head;while (k > 0) {if (p == null) {return null;}p = p.next;k--;}while (p != null) {p = p.next;head = head.next;}return head;}
}

快慢指针相关题目：

1、求链表的中间结点。当快指针走到链表末尾时，慢指针刚好走到链表的中点。
2、判断单链表是否有环。如果快指针追上慢指针，说明有环；反之，当快指针走到链表的结尾时还没有遇到慢指针，说明没有环。

这篇关于面试题15. 链表中倒数第k个结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---