[leetcode ladder] the penultimate node in the 022 linked list

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 .

Example 1：

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

 Input ：head = [1,2,3,4,5] , k=2
 Output ：[4,5]

Example 2：

 Input ：head = [1,2,3,4,5] , k=100
 Output ：[]

Example 3：

 Input ：head = [] , k=1
 Output ：[]

Topic link ：

The finger of the sword Offer 22. Last in the list k Nodes - Power button （LeetCode）https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/ Last in the list k Nodes _ Niuke Tiba _ Cattle from (nowcoder.com)https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

There are more test cases of Niuke here , I recommend you to use Niuke brush ！

---

Their thinking ：

Conventional method 1： Sooner or later

This is a very classic approach , It is the deformation operation of fast and slow pointer . We set two pointers , Where the pointer late Than the pointer early Go early k Step , Then let the pointer early With the pointer late Common backward traversal , When the pointer late Point to NULL when , The pointer early The node pointed to happens to be the penultimate k Nodes .

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* late = head;
    struct ListNode* early = head;
    while(k--)
    {
        if(late!=NULL) // When late Isn't empty ,late Go straight back 
            late=late->next;
        else
            return NULL;// When not full k Step late Have already walked to NULL when , Go straight back to NULL, Can't get the penultimate k Nodes 
    }
    while(late) //late The pointer and early The pointer goes all the way to late It stops when the pointer points to null 
    {
        early=early->next; //early Take a step back 
        late=late->next; //late Take a step backwards 
    }
    return early;
}

To sum up ： This is a very typical speed pointer problem , I believe you can remember this method by looking at it once , Very classic and easy to use ！