给定一个头结点为head的非空单链表,返回链表的中间结点。如果有两个中间节点,则返回第二个中间结点。
时间: 2024-08-12 09:06:48 浏览: 57
50.两个链表的第一个公共节点1
在给定一个非空单链表的情况下,找到链表的中间节点可以通过两个指针的方法来实现,通常称为“快慢指针”或“双指针法”。这个方法的核心思想是让一个指针每次移动两步(即“快指针”),另一个指针每次移动一步(即“慢指针”)。当快指针到达链表尾部时,慢指针正好位于中间节点或者离中间节点一步的距离。
以下是算法步骤:
1. 定义两个指针,`fast` 和 `slow`,初始时都指向头节点 `head`。
2. 使用循环进行遍历:
- 快指针 `fast` 每次迭代前进两个节点。
- 慢指针 `slow` 每次迭代前进一个节点。
3. 当快指针 `fast` 到达链表的末尾(即 `fast` 或 `fast->next` 为 `NULL`)时,慢指针 `slow` 就指向了链表的中间节点或者距离中间节点一步的地方。
4. 如果链表有两个中间节点,因为快指针已经到了末尾,慢指针就是第二个中间节点。
以下是伪代码表示:
```python
def findMiddleNode(head):
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
```
阅读全文