要找到单链表的中间节点,你可以使用双指针技巧,其中一个指针每次移动一个节点,另一个指针每次移动两个节点。
当快指针到达链表尾部时,慢指针就会指向链表的中间节点。
![如何找到单链表中间的节点 图片[1]-如何找到单链表中间的节点-不念博客](https://www.bunian.cn/wp-content/uploads/2023/11/image-133.png)
参考代码:
#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 -> 5ListNode* 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