题目描述补充

给定一个单链表的头节点 head，请编写一个函数来找到该链表的中点。链表中的节点定义如下（以 Python 为例，但概念适用于所有语言）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

函数签名应该类似于：

def findMiddle(head: ListNode) -> ListNode

该函数需要返回链表的中点节点。如果链表长度为偶数，则返回中间两个节点的第一个。

示例

假设链表为 1 -> 2 -> 3 -> 4 -> 5，则函数应该返回节点 3。

如果链表为 1 -> 2 -> 3 -> 4，则函数应该返回节点 2 或 3（根据实现，通常返回第一个中点）。

PHP 示例代码

<?php

class ListNode {
    public $val = 0;
    public $next = null;
    
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function findMiddle($head) {
    $slow = $head;
    $fast = $head;
    
    while ($fast != null && $fast->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    
    return $slow;
}

// 示例用法
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$middle = findMiddle($head);
echo $middle->val; // 输出 3
?>

Python 示例代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def findMiddle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# 示例用法
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 = findMiddle(head)
print(middle.val)  # 输出 3

JavaScript 示例代码

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function findMiddle(head) {
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

// 示例用法
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

let middle = findMiddle(head);
console.log(middle.val); // 输出 3

码小课网站中有更多相关内容分享给大家学习，包括链表操作、算法优化等进阶知识。