如何找到单链表中间的节点

要找到单链表的中间节点，你可以使用双指针技巧，其中一个指针每次移动一个节点，另一个指针每次移动两个节点。

当快指针到达链表尾部时，慢指针就会指向链表的中间节点。

参考代码：

#include <iostream>
struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};
ListNode* findMiddle(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;        // 慢指针每次移动一个节点
        fast = fast->next->next;  // 快指针每次移动两个节点
    }
    
    return slow;
}
int main() {
    // 创建一个单链表：1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    // 找到中间节点
    ListNode* middle = findMiddle(head);
    
    if (middle != nullptr) {
        std::cout << "中间节点的值为: " << middle->data << std::endl;
    } else {
        std::cout << "链表为空或长度为偶数，没有中间节点。" << std::endl;
    }
    
    // 释放链表内存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    
    return 0;
}
#include <iostream>

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};

ListNode* findMiddle(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;        // 慢指针每次移动一个节点
        fast = fast->next->next;  // 快指针每次移动两个节点
    }
    
    return slow;
}

int main() {
    // 创建一个单链表：1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    // 找到中间节点
    ListNode* middle = findMiddle(head);
    
    if (middle != nullptr) {
        std::cout << "中间节点的值为: " << middle->data << std::endl;
    } else {
        std::cout << "链表为空或长度为偶数，没有中间节点。" << std::endl;
    }
    
    // 释放链表内存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    
    return 0;
}

#include <iostream>

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};

ListNode* findMiddle(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;        // 慢指针每次移动一个节点
        fast = fast->next->next;  // 快指针每次移动两个节点
    }
    
    return slow;
}

int main() {
    // 创建一个单链表：1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    // 找到中间节点
    ListNode* middle = findMiddle(head);
    
    if (middle != nullptr) {
        std::cout << "中间节点的值为: " << middle->data << std::endl;
    } else {
        std::cout << "链表为空或长度为偶数，没有中间节点。" << std::endl;
    }
    
    // 释放链表内存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    
    return 0;
}