函数find_middle()实现了对给定的单链表,查找到其中间结点。如果中间结点为两个,返回前面的那个结点的地址。请完成该函数。 函数接口定义: Node* find_middle(Node* head); head是单链表的头指针,函数返回查找到的结点地址。
时间: 2024-03-20 16:39:06 浏览: 127
这道题的解法已经有了,这里给出另一种思路。
要返回中间结点,可以使用两个指针,一个慢指针 `slow`,一个快指针 `fast`,每次让 `slow` 前进 1 步,`fast` 前进 2 步,当 `fast` 到达链表结尾时,`slow` 就到达了链表的中间位置。如果链表长度是偶数,则需要返回前面的那个中间结点,可以通过设置一个标志位来判断链表长度的奇偶性。
代码如下:
```
Node* find_middle(Node* head) {
bool flag = false; // 标志位,表示链表长度是否为偶数
Node *slow = head, *fast = head;
while (fast->next) { // 注意判断条件是 fast->next,而不是 fast
slow = slow->next;
fast = fast->next->next;
if (!fast) {
flag = true; // 链表长度为偶数
break;
}
}
if (flag) {
return slow; // 链表长度为偶数,返回前面的那个中间结点
} else {
return slow->next; // 链表长度为奇数,返回中间结点
}
}
```
阅读全文