题目链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
- 笨方法：第一次循环算出链表的长度，长度和k相减就能得到是第几个节点。优点是容易想到，缺点是需要循环两次。最坏的情况就是K等于1的时候，需要完全遍历两次，复杂度2 O(N)
/**
* 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) {
int len = 0;
ListNode temp = head;
while (temp != null) {
len++;
temp = temp.next;
}
temp = head;
int index = len - k;
while (index-- > 0) {
temp = temp.next;
}
return temp;
}
}
- 聪明的方法：使用快慢指针，复杂度O(N)。
/**
* 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 frontNode = head, behindNode = head;
// 先走k个节点，剩下就还有len - k个节点
while (k-- > 0) {
frontNode = frontNode.next;
}
// 这里其实就是移动len - k个节点，刚好是倒数第K个节点
while (frontNode != null) {
frontNode = frontNode.next;
behindNode = behindNode.next;
}
return behindNode;
}
}
但两种题解执行结果好像并没有什么差别。
image.png
