如何找到链表的中间节点？

推荐答案

// www.javascriptcn.com code example
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

本题详细解读

问题描述

给定一个单链表，要求找到链表的中间节点。如果链表长度为偶数，则返回第二个中间节点。

解题思路

1. 快慢指针法：使用两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。当快指针到达链表末尾时，慢指针正好指向链表的中间节点。
2. 时间复杂度：O(n)，其中 n 是链表的长度。快指针遍历链表一次。
3. 空间复杂度：O(1)，只使用了常数级别的额外空间。

代码实现

// www.javascriptcn.com code example
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

示例

假设链表为 1 -> 2 -> 3 -> 4 -> 5，则中间节点为 3。

// www.javascriptcn.com code example
# 创建链表
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# 找到中间节点
middle = find_middle(head)
print(middle.val)  # 输出: 3

注意事项

• 如果链表为空，直接返回 None。
• 如果链表长度为偶数，返回第二个中间节点。例如，链表 1 -> 2 -> 3 -> 4 的中间节点为 3。