剑指 Offer 22. 链表中倒数第k个节点

题目链接：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;
    }
}

但两种题解执行结果好像并没有什么差别。