Sword finger offer 22 The penultimate node in the linked list - speed pointer

One 、 Title Description

Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes .

for example , A list has 6 Nodes , Start from the beginning , Their values, in turn, are 1、2、3、4、5、6. The last of the list 3 Each node has a value of 4 The node of .

Example 1：

 Given a linked list : 1->2->3->4->5,  and  k = 2.

 Back to the list  4->5.

Two 、 Problem solving

Speed pointer

There is a difference between the speed pointer and the slow pointer K Nodes , Then update the speed pointer

/** * 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) {
    
        // Speed pointer 
        if(head == null){
    
            return head;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0;i<k;i++){
    
            fast = fast.next;
        }
        while(fast != null){
    
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}