面试题22. 链表中倒数第k个节点
题目描述
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
题目分析
这题没想到很好的方法，只是遍历了一次链表，获取链表的长度，然后获取第size-k个节点，时间复杂度也还是O（N），但是仔细一想，这样的题目应该不会出现在剑指Offer里，然后翻了一下题解，刚好第一个就是CXX同学新鲜滚热辣刚写出来的，看了标题就想起一个大一的时候了解过的快慢指针思想（很惭愧大二上修完数据结构之后就没有刷过题了现在什么都不会了），然后就开始继续马马马...
言归正传，其实快慢指针法和我那个“没那么好的”方法其实是一样的，我的第一轮遍历相当于快指针，先走到尾部的null，计算出走出的步数，然后第二轮遍历只要走到第一轮遍历的前k个节点就好，也就是倒数第k个节点，而快慢指针做法里的慢指针相当于我的第二轮遍历，因为慢指针比快指针落后了k步，所以快指针到达null的时候，慢指针刚好走到null的前k个节点，也恰恰是倒数第k个节点。两种方法都能得出正确的答案，时间复杂度都是O(N)，都需要走2N-K步，但是能够将快慢指针的思想灵活运用到题目当中，这是CXX牛皮的地方，正如他所说的，刷题，共勉！
//快慢指针做法
fun getKthFromEnd(head: ListNode?, k: Int): ListNode? {
var fast = head
var slow = head
var n = k
while(n>=1){
n--
fast = fast?.next
}
while(fast!=null){
fast = fast.next
slow = slow?.next
}
return slow
}
//蛮力法
fun getKthFromEndForce(head: ListNode?, k: Int): ListNode? {
var size = 0
var node = head
while(node != null){
size++
node = node.next
}
size-=k
node = head
while(size!=0){
size--
node = node?.next
}
return node
}
暴力法
快慢指针法
