小企业网站建设哪些好办,网址域名查询网,Linux网站建设总结,wordpress dockerfile876. 链表的中间结点 算法 快慢指针 题目特征 需要对链表中的节点进行遍历#xff0c;并且需要根据节点之间的相对位置或者距离进行操作 题目链接#xff1a;https://leetcode.cn/problems/middle-of-the-linked-list/
算法 快慢指针 题目特征 需要对链表中… 876. 链表的中间结点 算法 快慢指针 题目特征 需要对链表中的节点进行遍历并且需要根据节点之间的相对位置或者距离进行操作 题目链接https://leetcode.cn/problems/middle-of-the-linked-list/
算法 快慢指针 题目特征 需要对链表中的节点进行遍历并且需要根据节点之间的相对位置或者距离进行操作
思路用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步fast 一次走两步。那么当 fast 到达链表的末尾时slow 必然位于中间。
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow, head nullptr;while (fast ! nullptr fast-next ! nullptr) {slow slow-next;fast fast-next-next;}return slow;}
};细节处理如果有两个中间结点则返回第二个中间结点。
对于一个偶数长度的链表假设链表中有 6 个节点节点分别为 1 - 2 - 3 - 4 - 5 - 6。
当 slow 和 fast 初始都指向链表的头节点时slow 每次移动一步fast 每次移动两步。
第一步slow 移动到节点 2fast 移动到节点 3。第二步slow 移动到节点 3fast 移动到节点 5。第三步slow 移动到节点 4fast 移动到节点 6。
此时fast 到达了链表的末尾slow 位于链表的中间位置即节点 4。
根据这个例子我们可以看到当链表长度为偶数时slow 确实返回的是中间的第二个节点即节点 4。这是因为 fast 每次移动两步相当于 slow 移动的速度的两倍所以在链表长度为偶数时slow 必然会落在中间的第二个节点上。
如果希望返回中间的第一个节点可以在初始化时让 fast 指向链表的第一个节点然后进行相同的遍历操作。这样当 fast 到达链表的末尾时slow 就会指向中间的第一个节点。 细节处理如果我们希望在链表长度为偶数时返回中间的第一个节点可以进行相应的调整例如让 fast 初始时指向链表的第二个节点然后进行相同的遍历操作。这样当 fast 到达链表末尾时slow 就会指向中间的第一个节点。
对于一个偶数长度的链表假设链表中有 6 个节点节点分别为 1 - 2 - 3 - 4 - 5 - 6。
当 slow 初始指向链表的头节点fast 初始指向链表的第二个节点时slow 每次移动一步fast 每次移动两步。
第一步slow 移动到节点 1fast 移动到节点 3。第二步slow 移动到节点 2fast 移动到节点 5。第三步slow 移动到节点 3fast 移动到节点 6。
此时fast 到达了链表的末尾slow 位于链表的中间位置即节点 3。
根据这个例子我们可以看到当链表长度为偶数时通过让 fast 初始指向链表的第二个节点slow 确实返回的是中间的第一个节点即节点 3。
所以通过调整 fast 初始位置我们可以控制在链表长度为偶数时返回中间的第一个节点还是第二个节点。
