[sword finger offer] 22 The penultimate node in the linked list

The finger of the sword Offer 22. Last in the list K node

subject

Ideas

• Initialize a front pointer former And a back pointer latter, Both pointers point to the header node head
• The front pointer moves forward first K Step ,（ After that , Double pointer former and latter Distance between k Step ）
• Then the two pointers move at the same time ,former and latter Take a step forward , until former Pointing empty , So now Latter The difference from the tail node k - 1 Step , That is to point to the penultimate k Nodes .

Code

/** * 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;

        //  The first pointer goes first k Step 
        for(int i = 0; i < k; i++)
        {
    
            if(former == null)
            {
    
                return null;
            }
            former = former.next;
        }

        //  Then the first pointer differs from the second pointer k Step   Because the first pointer former stay  k + 1 Location  latter Still in the first position 

        //  When the first pointer jumps out  former Pointing empty   that latter and former Difference between k Step , That is, the difference from the tail node k - 1 Step 
        while(former != null)
        {
    
            //  Move the first pointer to the end of the linked list 
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}