剑指offer系列之十三：链表中的倒数第k个节点

本文主要是介绍剑指offer系列之十三：链表中的倒数第k个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

举一个简单的例子，比如链表{1,2,3,4,5}，如果要返回倒数第二个节点，也就是k=2，就相当于正数第5-k+1=4个节点，所以我们可以采用两次循环：一次循环得到链表的结点个数；另一次循环则是从链表中找到第n-k+1个节点。虽然是两次循环，但时间复杂度是 $O(n)$ ，需要注意的是，这里仍然需要对链表的边界条件进行判断。基于这种思路写出如下代码：

public ListNode FindKthToTail(ListNode head,int k) {if(head == null || k <= 0) return null;int nodesNum = 1;ListNode node = head;while(node.next != null){nodesNum++;node = node.next;}int i = 1;node = head;while(k <= nodesNum && i != nodesNum - k + 1){i++;node = node.next;}if(k <= nodesNum)return node;return null;}

还有一种思路就是创建两个指针，一个指针先走k-1部，当第k部的时候，另一个指针从第一个节点开始走，这样，第一个指针到达最后一个指针的时候，第二个指针刚好到达倒数第k个节点的位置。实现代码如下（已被牛客AC）：

public ListNode FindKthToTail2(ListNode head,int k) {if(head == null || k <= 0) return null;ListNode pre = head;ListNode behind = null;for (int i = 0; i < k - 1; i++) {if(pre.next != null){pre = pre.next;}else {return null;}}behind = head;while(pre.next != null){pre = pre.next;behind = behind.next;}return behind;}