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

题目

思路

• 初始化一个前指针former和一个后指针latter，两个指针都指向头节点head
• 前指针先向前走K步，（结束之后，双指针former和latter间相距k步）
• 之后两个指针同时进行移动，former和latter都向前走一步，直到former指向空，那们此时Latter和尾节点相差k - 1步，也就是指向倒数第k个节点。

代码

/** * 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 former = head;
        ListNode latter = head;

        // 第一个指针先走k步
        for(int i = 0; i < k; i++)
        {
    
            if(former == null)
            {
    
                return null;
            }
            former = former.next;
        }

        // 那么第一个指针与第二个指针相差k步 因为此时第一个指针former在 k + 1位置 latter还在第一个位置

        // 当第一个指针跳出之后 former指向空 那么latter和former相差k步，那们也就是和尾部节点相差k - 1步
        while(former != null)
        {
    
            // 将第一个指针移动到链表尾部
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}