Leetcode skimming: the penultimate node in the linked list

1. The... In the linked list k Nodes

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 .
Be careful ： This question once appeared in meituan's written test algorithm question .
Example ：

1. Hash table implementation

Here we can use hash table to solve this problem ：
First traverse the list , Store the nodes in the linked list in the hash table in the form of key value pairs , The key of the hash table is the location of the node （ from 1 Start ）, The value is the current node , Because of the penultimate k The node is exactly the positive number n-k+1 individual （n Is the length of the linked list ）, So the index in the hash table is n-k Of value, Take it out of the hash table and return it .
The specific code is as follows ：

/** * 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) {
    
        Map<Integer,ListNode> hash=new HashMap<>();
        ListNode p=head;
        int num=1;
        while(p!=null){
    
            hash.put(num,p);
            p=p.next;
            num++;
        }
        p=hash.get(num-k);
        return p;
    }
}

2. Time complexity analysis

Because time is a traversal of the linked list , So the time complexity is $O(n)$, Here, a hash table is used to store the corresponding linked list location and linked list node , So the complexity of space is $O(n)$, The specific code is in LeetCode The implementation of is as follows ：

3. In order to find

According to the previous analysis , Last but not least k The first element node is the positive number n-k+1 Nodes , So the key to the problem is to find out the total number of linked list nodes first n, Point the pointer to the n-k+1 The problem can be solved by adding a linked list node and returning , The specific code is as follows ：

/** * 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) {
    
        int n=0;
        ListNode p=null;
        // Determine the length of the linked list 
        for(p=head;p!=null;p=p.next){
    
            n++;
        }
        p=head;
        for(int i=0;i<n-k;i++){
    
            p=p.next;
        }
        return p;
    }
}

Be careful ： Find the first n-k+1 When there are linked list nodes , because p Point again to head Head node , For the first element , So just move n-k This can point to the... Of the linked list n-k+1 Nodes .

4. Time complexity analysis

Because the implementation time of this algorithm is still the traversal of the linked list , The first traversal is to determine the length of the linked list , The second iteration is to find the second n-k+1 List nodes . So the time complexity is still $O(n)$, The hash table storage node is not used in this algorithm implementation , So the space complexity is zero $O(1)$, The specific algorithm is LeetCode The implementation of is as follows ：

5. Fast and slow pointer to achieve

The idea of fast and slow pointer . We will the first pointer \textit{fast}fast The list points to k + 1 Nodes , The second pointer $\text{slow}$ Point to the first node of the list , Now the pointer $\text{fast}$ And $\text{slow}$ There is just a gap between the two $k$ Nodes . At this time, the two pointers move backward synchronously , When the first pointer $\text{fast}$ When you reach the empty node at the end of the linked list , Now $\text{slow}$ The pointer just points to the penultimate... Of the linked list $k$ Nodes .
Let's start with $\text{fast}$ Point to the head node of the list , Then walk back $k$ Step , Now $\text{fast}$ The pointer just points to the... Of the linked list $k+1$ Nodes .
Let's start with $\text{slow}$ Point to the head node of the list , meanwhile $\text{slow}$ And $\text{fast}$ Step backward synchronously , When $\text{fast}$ When the pointer points to the empty node at the end of the linked list , Then return to $\text{slow}$ Point to the node .
The specific code is as follows ：

/** * 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 fast=head;
        ListNode slow=head;
        // take fast The pointer moves forward k position 
        while(fast!=null && k>0){
    
            fast=fast.next;
            k--;
        }
        // Move the speed pointer backward at the same time 
        while(fast!=null){
    
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

6.GIF Moving pictures show

Here's a list {1,2,3,4,5} For example , Look for the last 2 An element of GIF The dynamic diagram is as follows ：

7. Time complexity analysis

The implementation of this algorithm , Here is still only the traversal of the linked list , So the time complexity is zero $O(n)$, The space complexity is $O(1)$. The specific code is in LeetCode The implementation of is as follows ：