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

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

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

图片[1]-如何找到单链表中间的节点-不念博客

参考代码:

#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; }
© 版权声明
THE END