活动地址：CSDN21天学习挑战赛

Application of fast and slow pointers in linked lists

Leetcode876——链表的中间结点

题目描述

给定一个头结点为 head 的非空单链表,返回链表的中间结点.
如果有两个中间结点,则返回第二个中间结点.

链接：Leetcode876

示例

示例 1：
输入：[1,2,3,4,5] **输出：**此列表中的结点 3

示例 2：
输入：[1,2,3,4,5,6] **输出：**此列表中的结点 4

提示：

• 给定链表的结点数介于 1 和 100 之间.

核心代码模式

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */


struct ListNode* middleNode(struct ListNode* head)
{
    
    
}

Thought analysis and code implementation（C语言）

1.Divide by the length of the linked list2法

这个方法很简单,先遍历一遍链表,Use a counter to record the length of the linked list,divide the length by2is the number of steps to move,Then traverse the list looking for intermediate nodes.

代码实现

struct ListNode* middleNode(struct ListNode* head)
{
    
    int cnt = 0;
    struct ListNode* cur = head;
    struct ListNode* mid = head;
    while(cur)
    {
    
        cnt++;
        cur = cur->next;
    }
    cnt /= 2;
    while(cnt--)
    {
    
        mid = mid->next;
    }
    return mid;
}

2.快慢指针（二倍速）

顾名思义,It's two pointers, one goes ahead first.,walk behind the other,Are you looking for an intermediate node?,Then let the fast pointer go two steps at a time,慢指针一次走一步,The fast pointer moves twice as many steps as the slow pointer.,那好,When the fast pointer goes to the end of the linked list, does the slow pointer go to the middle?,However, the processing method of the tail must be determined according to whether the length of the linked list is odd or even..This method is slightly better than the above method,is one less traversal.

代码实现

struct ListNode* middleNode(struct ListNode* head)
{
    
    struct ListNode* fast = head;
    struct ListNode* slow = head;
   
    while(fast && fast->next)
    {
    
        fast = fast->next->next;
        slow = slow->next;
    }
    
    return slow;
}

Leetcode JZ22——链表中倒数第k个结点

题目描述

输入一个链表,输出该链表中倒数第k个节点.为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点.
例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6.这个链表的倒数第 3 个节点是值为 4 的节点.

链接：Leetcode *offer22

示例：
给定一个链表: 1->2->3->4->5, 和 _k _= 2. 返回链表 4**->5**.

核心代码模式

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    

}

思路分析与代码实现（C语言）

One idea is to traverse and use the counter to find the length of the linked list,然后用它减去kget the number of steps to move,Then move a pointer to the corresponding position.

We consider using fast and slow pointers here,可能有人会问了,how to use this？The speed pointer does not necessarily mean walking fast or slow,Can be a quick pointer to start first,Start after slow pointer.在这里,先让快指针移动k步,In this case, the distance between the fast pointer and the slow pointer at the beginning isk-1,At this time, let the fast and slow pointer move together,直到快指针指向NULL,At this time, the position pointed to by the slow pointer from the end of the linked list is the penultimatek位了.

However, the linked list related topics must pay attention to some details,In particular the issue of possible null pointers and wild pointers should be considered,It have a potential problem here？有,如果链表为空,那么fast一开始就是NULL,如果直接让fast向后移动k步的话,会出现fast = fast->next语句,will dereferenceNULL指针了,就会出问题,This is we want to consider the point of alert,所以要先加上一个判断if(fast == NULL),如果为空就直接返回NULL.

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(k--)
    {
    
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    
    while(fast)
    {
    
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}