题目

在这里插入图片描述

思路1(暴力求解)

既然让我们求中间的节点，我们可以先遍历一遍求出整个链表的节点个数N，再遍历到N/2+1，当前位置就是中间节点的位置，虽然这样的时间复杂度是O(n)但是这样需要遍历两次，我们有一个更巧妙的方法

思路2(快慢指针)

我们可以i定义两个指针，fast和slow，fast每次走2个节点，slow每次走1个节点
如果是奇数个节点的话，当fast的下一个节点是空节点时，slow走到的当前节点就是中间节点
如果是偶数个节点的话，当fast当前的节点是空节点时，slow走到的当前节点就是中间节点
在这里插入图片描述
代码实现

struct ListNode* middleNode(struct ListNode* head){if (head == NULL || head->next == NULL) return head;struct ListNode* fast = head, *slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

在这里插入图片描述

总结

快慢指针是一种常用的链表指针操作技巧，可以在链表中解决很多问题。下面是一些可以使用快慢指针的常见场景：

判断链表是否有环：快慢指针可以用来判断一个链表是否有环。将慢指针移动一步，快指针移动两步，如果存在环，两个指针最终会相遇。这个技巧被称为快慢指针法或者龟兔赛跑算法。
查找链表的中间节点：使用快慢指针可以查找链表的中间节点。将慢指针移动一步，快指针移动两步，当快指针到达链表末尾时，慢指针刚好在链表中间。
链表倒数第k个节点：使用快慢指针也可以查找链表的倒数第k个节点。将快指针移动k-1步，然后将快慢指针一起移动，当快指针到达链表末尾时，慢指针所指的节点就是倒数第k个节点。
删除链表的倒数第n个节点：可以使用快慢指针删除链表的倒数第n个节点。先将快指针移动n步，然后将快慢指针一起移动，当快指针到达链表末尾时，慢指针所指的节点就是要删除的节点。

上一篇：5.docker入门到精通—安装redis集群（理论）

下一篇：AES加密算法原理及C++代码，每步均有相应代码

876. 链表的中间结点

文章目录

题目

思路1(暴力求解)

思路2(快慢指针)

总结

相关内容

热门资讯