876 链表的中间节点
要做出这道题不难,只需掌握「快慢指针」的概念:fast走两步,slow走一步
但是需要注意以下几点:
- 判断条件为
fast!=nullptr && fast->next!=nullptr - 当fast初始化为head,链表个数为奇数,最后指针
fast到达链表最后一个元素;链表个数为偶数,最后指针指向末尾的nullptr slow指向链表中间节点,如果有两个中间节点,则指向靠后的那一个
如何计算指向中间哪个节点
方法如下:
- 将链表第1个节点索引标记为0,而不是1
- 假设链表最后一个节点索引为n,链表长度len = n + 1
- 中间节点索引 idx = len / 2 (这里是程序中的短除)
举个例子:
- 第一个链表, len = 5, 中间节点 idx = 5 / 2 = 2
- 第二个链表, len = 6, 中间节点 idx = 6 / 2 = 3
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast = head, * slow = head;
// 注意不要遗漏fast->next != nullptr
// 这两个条件使得fast指向链表尾部的下一个元素(nullptr)
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};