一个单向链表, 请你找出中间节点要求只能遍历一遍.
时间: 2024-03-13 09:46:59 浏览: 13
要找出单向链表的中间节点,可以使用快慢指针的方法,快指针每次向前移动两个节点,慢指针每次向前移动一个节点,当快指针到达链表尾部时,慢指针所指向的节点就是中间节点。
具体实现如下(假设链表节点的结构体定义为ListNode):
```c++
ListNode* findMiddleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
```
时间复杂度为O(n),只需要遍历一遍链表即可找到中间节点。
相关问题
一个单向链表,已知p节点其他位置.请你删除p节点
要删除单向链表中的节点p,我们需要找到其前一个节点pre,然后将pre的next指针指向p的下一个节点,即跳过p节点,最后释放p节点的内存即可。具体实现如下(假设链表节点的结构体定义为ListNode):
```c++
void deleteNode(ListNode* p) {
if(!p) return; // p为空指针,直接返回
if(!p->next) { // p为尾节点,需要遍历找到pre
ListNode* cur = head;
while(cur && cur->next != p) {
cur = cur->next;
}
if(cur) cur->next = nullptr;
delete p;
return;
}
// p不为尾节点,直接删除
ListNode* next = p->next;
p->val = next->val;
p->next = next->next;
delete next;
}
```
需要注意的是,如果p为尾节点,则需要遍历整个链表找到其前一个节点pre,时间复杂度为O(n);如果p不为尾节点,则可以直接删除,时间复杂度为O(1)。
c++遍历单向链表并返回链表某一节点
以下是遍历单向链表并返回链表某一节点的示例代码:
```c++
struct Node {
int data;
Node* next;
};
Node* findNode(Node* head, int val) {
Node* curr = head;
while (curr != nullptr) {
if (curr->data == val) {
return curr;
}
curr = curr->next;
}
return nullptr;
}
```
在上述示例代码中,我们首先定义了一个 `Node` 结构体,其中包含了一个整型变量 `data` 和一个指向下一个节点的指针 `next`。
接下来,我们定义了一个名为 `findNode` 的函数,该函数接收两个参数:一个指向链表头节点的指针 `head` 和一个需要查找的值 `val`。在函数中,我们使用一个 `curr` 指针来遍历整个链表,如果当前节点的值等于需要查找的值,那么就返回该节点的指针;否则,继续遍历下一个节点。如果整个链表都遍历完了还没有找到需要查找的值,那么就返回 `nullptr` 表示未找到。
使用示例:
```c++
int main() {
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
Node* node = findNode(head, 2);
if (node != nullptr) {
std::cout << "Found node with value " << node->data << std::endl;
} else {
std::cout << "Node not found" << std::endl;
}
return 0;
}
```
在上述示例中,我们首先创建了一个包含三个节点的链表,然后调用 `findNode` 函数查找值为 2 的节点。如果找到了,则输出该节点的值;否则,输出“Node not found”。