跳转至

876 链表的中间节点

要做出这道题不难,只需掌握「快慢指针」的概念:fast走两步,slow走一步

但是需要注意以下几点:

  1. 判断条件为fast!=nullptr && fast->next!=nullptr
  2. 当fast初始化为head,链表个数为奇数,最后指针fast到达链表最后一个元素;链表个数为偶数,最后指针指向末尾的nullptr
  3. slow指向链表中间节点,如果有两个中间节点,则指向靠后的那一个
如何计算指向中间哪个节点

方法如下:

  1. 将链表第1个节点索引标记为0,而不是1
  2. 假设链表最后一个节点索引为n,链表长度len = n + 1
  3. 中间节点索引 idx = len / 2 (这里是程序中的短除)

举个例子:

picture 0

  • 第一个链表, 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;
    }
};