查找一个长度大于2的单链表的中间位置结点

Question

查找一个长度大于2的单链表的中间位置结点
查找一个长度大于2的单链表的中间位置结点

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

在单链表中查找中间位置的节点可以通过快慢指针法实现，也叫Floyd算法或者快慢指针算法。在这种方法中，我们使用两个指针，一个指针快（每次移动两步），另一个指针慢（每次移动一步）。当快指针到达链表的末尾时，慢指针将指向链表的中间位置。下面是一段可能的Python代码实现：

假设我们的链表节点结构定义如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

我们可以用下面的方法来找到链表的中间节点：

def find_middle_node(head):
    if head is None or head.next is None:  # 链表为空或只有一个节点，返回None或者该节点
        return head
    slow = head  # 慢指针从头节点开始
    fast = head  # 快指针从头节点开始，初始时快慢指针重合
    while fast is not None and fast.next is not None:  # 快指针未到达链表末尾
        slow = slow.next  # 慢指针每次移动一步
        fast = fast.next.next  # 快指针每次移动两步
    return slow  # 返回慢指针指向的节点，即中间节点

这个函数返回的是链表的中间节点。如果链表长度是偶数，这个函数会返回第二个中间的节点。如果你希望处理偶数长度的情况并返回两个中间节点中的第一个，你可以在快指针的循环中添加一个额外的检查条件 fast.next.next is not None。如果链表长度是奇数，那么返回的节点就是中间的节点。如果链表长度是偶数，返回的节点是后半部分的第一个节点。