优化以下代码Node* find_middle(Node* head) { Node *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
时间: 2024-04-05 13:29:58 浏览: 8
这段代码已经是比较优化的了,时间复杂度为 $O(n)$,空间复杂度为 $O(1)$,是一种比较高效的方法。
不过如果一定要说有哪些小的优化,可以考虑在循环条件中使用 `fast->next->next`,而不是先判断 `fast` 是否为空,再判断 `fast->next` 是否为空。这样可以减少判断的次数,但是实际上对于链表长度比较小的情况,这种优化的效果不大。
还可以在循环内部增加判断,当 `fast` 或 `fast->next` 为空时,跳出循环。这样可以减少不必要的循环次数,但是同样对于链表长度比较小的情况,效果不大,而对于长度比较大的链表,实际上已经达到了 $O(n)$ 的时间复杂度,效果也不是很明显。
相关问题
函数find_middle()实现了对给定的单链表,查找到其中间结点。如果中间结点为两个,返回前面的那个结点的地址。请完成该函数。 函数接口定义: Node* find_middle(Node* head); head是单链表的头指针,函数返回查找到的结点地址。
这道题的解法已经有了,这里给出另一种思路。
要返回中间结点,可以使用两个指针,一个慢指针 `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; // 链表长度为奇数,返回中间结点
}
}
```
函数find_middle()实现了对给定的单链表,查找到其中间结点。如果中间结点为两个,返回前面的那个结点的地址。请完成该函数。 函数接口定义: Node* find_middle(Node* head); head是单链表的头指针,函数返回查找到的结点地址。 裁判测试程序样例: #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct ListNode { int num; struct ListNode *next; }Node; Node *createlist(); /*裁判实现,细节不表*/ Node* find_middle(Node* head); void display(Node *head);/*裁判实现,细节不表*/ int main() { Node *head,*p; head = createlist(); p = find_middle(head); display(p); return 0; } /* 请在这里填写答案 */ 输入样例1: 5 1 3 7 9 10 输出样例1: 7
```
Node* find_middle(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)