如何以最简方式查找Linked List中间节点？附相关代码

嘿，我来分享一下查找链表中间节点最简洁高效的实现思路——快慢指针法，这是目前公认的最优解，时间复杂度O(n)，空间复杂度O(1)，完全不需要额外统计链表长度或者用栈之类的辅助结构。

方法原理 #

核心逻辑特别直观：

• 初始化两个指针，slow（慢指针）和fast（快指针），都从链表的head节点出发
• 慢指针每次走1步，快指针每次走2步
• 当快指针走到链表末尾（fast为None或者fast.nextNode为None）时，慢指针刚好指向链表的中间节点
  • 如果链表节点数是奇数，慢指针就是正中间的节点
  • 如果是偶数，慢指针会停在中间两个节点里靠左的那个（想靠右的话微调循环条件即可）

结合你的代码实现 #

在你的LinkedList类里添加如下方法就能直接用：

class Node:
    def __init__(self, data, nextNode=None):
        self.data = data
        self.nextNode = nextNode
    def getData(self):
        return self.data
    def setData(self, val):
        self.data = val
    def getNextNode(self):
        return self.nextNode
    def setNextNode(self, val):
        self.nextNode = val

class LinkedList:
    def __init__(self, head=None):
        self.head = head
        self.size = 0
    def getSize(self):
        return self.size  # 补全你未写完的部分
    
    # 新增：查找中间节点的方法
    def getMiddleNode(self):
        # 处理空链表的边界情况
        if not self.head:
            return None
        
        slow = self.head
        fast = self.head
        
        # 循环条件：快指针还能继续走两步
        while fast and fast.getNextNode():
            slow = slow.getNextNode()
            fast = fast.getNextNode().getNextNode()
        
        return slow

小测试示例 #

比如你构建链表：1 -> 2 -> 3 -> 4 -> 5，调用getMiddleNode()会返回值为3的节点；如果是1 -> 2 -> 3 -> 4，会返回值为2的节点（要是想返回3，只需要把循环条件改成while fast.getNextNode() and fast.getNextNode().getNextNode()就行）。

这个方法之所以简洁，是因为它只需要一次遍历就能定位中间节点，不用先统计长度再走半程，代码少还高效。

内容的提问来源于stack exchange，提问作者Sedat Özdemir