😈 Blog home page: 🐼 Hello, everyone. My name is classmate Zhang🐼
💖 Welcome to praise 👍 Collection 💗 Leaving a message. 📝 Welcome to discuss! 👀
🎵 This article was originally written by [Hello, my name is classmate Zhang] and started at CSDN 🌟🌟🌟
✨ Boutique column (updated from time to time) [data structure + algorithm] [notes][C language programming learning]
☀️ Boutique article recommendation
[advanced learning notes of C language] III. detailed explanation of string function (1) (sorting out liver explosion and hematemesis, recommended collection!!!)
[notes on basic learning of C language] + [notes on advanced learning of C language] summary (persistence is the only way to gain!)

preface

Why write brush notes?
The process of blogging is also a sort and summary of the process of brushing questions. It is a time-consuming but effective method.
When the blog you share helps others, it will bring you extra happiness and happiness.
(the happiness of topic brushing + the happiness of blog is simply double the reward. Double the happiness has wood and QAQ 🙈)

Topic content

Input a linked list and output the penultimate node in the linked list. In order to conform to the habit of most people, this question starts from 1, that is, the tail node of the linked list is the penultimate node.
For example, a linked list has six nodes. Starting from the beginning, their values are 1, 2, 3, 4, 5 and 6. The penultimate node of the linked list is a node with a value of 4.

Original question link (click to jump)

Traversal linked list method

The single linked list requires the penultimate node. Due to the unidirectional relationship between nodes, it is not easy to find it directly. However, if we convert the reciprocal to the ordinal, we can easily implement it by traversing the linked list from the node. See the diagram for the specific process.

Algorithm diagram

Function implementation

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    int length = 0;//Find the length of the linked list
    struct ListNode* cur = head;
    while(cur){
        length++;
        cur = cur->next;
    }
    cur = head;//cur returns the header node again
    int step = length-k;//The length+1-k position only needs to go backward by length-k step
    while(step--){
        cur = cur->next;
    }
    return cur;
}

Note: the default size of k in the leetcode title is less than length. If this condition is not given in practice, we need to add the following condition judgment Code:

 if(k > length)
        return NULL;

For example, in niuke.com, you can't pass without this judgment, which will prompt you for paragraph error.

After adding judgment statement

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    int length = 0;//Find the length of the linked list
    int step = 0;
    struct ListNode* cur = pListHead;
    while(cur){
        length++;
        cur = cur->next;
    }
    if(k > length)
        return NULL;
    cur = pListHead;//cur returns the header node again
    step = length-k;//The length+1-k position only needs to go backward by length-k step
    while(step--){
        cur = cur->next;
    }
    return cur;
}

Fast and slow pointer method

We can also use the fast and slow pointer method to find the penultimate node in the linked list. We can first let the fast pointer fast go k steps, and then the fast and slow pointers (fast and slow) go back together. When the fast pointer fast goes to the last NULL position, the slow pointer just goes to the penultimate position.

Algorithm diagram

Function implementation

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode *fast = head,*slow = head;
    while(k--){//fast k steps first
        fast = fast->next;
    }
    while(fast){//fast and slow go back together
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

If we do this problem on niuke.com, we need to consider more boundaries when using the fast and slow pointer method, and adjust the above code accordingly as follows:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode *fast = pListHead,*slow = pListHead;
    if(k == 0)//The conditional judgment of k=0 is added here
        return NULL;
    while(k--){//fast k steps first
        if(fast == NULL)//The judgment of fast going to NULL in advance is added here
        return NULL;
        fast = fast->next;
    }
    while(fast){//fast and slow go back together
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}