leetcode之剑指Offer22题，链表中倒数第k个节点。采用双指针的算法来完成。

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

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

1给定一个链表: 1->2->3->4->5, 和 k = 2.
2
3返回链表 4->5.

思路

第一思考哈希表，通过[key, value]的形式保存[位置, 对应结点],但是空间复杂度是o(n)。

第二思考，本质是也可以是求正序的n + 1 - k的结点，可以先遍历一次求得链表总长度，然后在遍历求得对应结点

第三思考，由于第二思考是两次循环，如果引入双指针可以解决

  1. 存在两个快慢指针，快指针会先移动k - 1个结点
  2. 之后，两个快慢指针同时移动，快慢指针每次移动一个单位，直到快指针的下一个结点为null

解题

 1/**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode(int x) { val = x; }
 7 * }
 8 */
 9class Solution {
10    //双指针
11    public ListNode getKthFromEnd(ListNode head, int k) {
12        if(null == head || k < 1) return null;
13        ListNode fast = head;
14        ListNode slow = head;
15        
16        int count = -1;
17        boolean flag = false;
18        while(null != fast)
19        {
20            fast = fast.next;
21            count++;
22            if(count == k - 1)
23            {
24                flag = true;
25                break;
26            }
27        }
28        //如果k比总长度要大，那么也找不到
29        if(!flag)
30        {
31            return null;
32        }
33
34        while(null != fast)
35        {
36            fast = fast.next;
37            slow = slow.next;
38        }
39        return slow;
40    }
41}