LeetCode876 --- 剑指Offer 22

非空链表，我们不需要判断为空的条件。

需要得到链表的中间节点，也许会想到，将链表遍历一遍，求出长度，再遍历一遍得到中间节点。如果只能遍历一遍呢？中间节点，也就是链表长的二分之一，那就可以通过定义两个指向，都从head开始向后遍历。fast一次向后挪两个节点，slow一次向后挪动一个节点。当fast为null或者fast.next为null，代表着fast已经走到终点，而此时的slow恰好就遍历了一半链表，此时slow就处于中间节点的位置。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;

        while( fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

几乎和上面一致，不过此时的slow和fast起点不同，因为当fast到重点时，slow要比fast少k-1步。fast和slow每次都走一步，因为它们的距离差已经确定，所以速读要一致。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {

        if(head==null){
            return null;
        }

        ListNode fast=head;
        ListNode slow=head;

        while(k-1>0){
            if(fast==null || fast.next==null){
                return null;
            }
            fast=fast.next;
            k--;
        }

        while(fast!=null && fast.next!=null){
                fast=fast.next;
                slow=slow.next;
        }

        return slow;

    }
}