华为OD机试 - 单向链表中间节点（Java & JS & Python & C & C++），华为OD机试，单向链表中间节点的Java、JS、Python、C、C++解法

摘要：华为OD机试中有一道关于单向链表中间节点的题目，要求使用Java、JavaScript、Python、C和C++等编程语言实现。该题目旨在考察候选者对链表操作以及不同编程语言的掌握程度。需要找到单向链表的中间节点，可以通过快慢指针法或使用循环遍历链表来实现。不同语言实现的具体语法和细节可能有所不同，但核心思路是相似的。

大家好，本题目库完全免费提供，但为了防范爬虫，我们暂时采取了收费措施，请大家订阅专栏后，可以私信联系我们进行退款，非常感谢大家的理解与支持。

文章目录

须知

题目描述

输出描述

解析

代码实现

题目描述

给定一个单向链表 L，请编写程序输出 L 中的中间节点保存的数据，如果链表中有两个中间节点，则输出第二个中间节点保存的数据。

给定的链表 L 为 1→7→5，则输出应为 7；给定的链表 L 为 1→2→3→4，则输出应为 3。

输入描述

每个输入包含一个测试用例，每个测试用例的第一行给出链表首节点的地址和一个正整数 N（N ≤ 10^5），表示结点的总数，结点的地址是5位非负整数，NULL地址用-1表示，接下来的 N 行，每行包含以下格式的信息：Address Data Next，Address 是结点地址，Data 是该结点保存的整数数据（0 ≤ Data ≤ 10^8），Next 是下一结点的地址。

输出描述

针对每个测试用例，程序应输出中间节点保存的数据，如果链表中有两个中间节点，则输出第二个中间节点保存的数据。

解析

为了找到链表的中间节点，我们可以使用快慢指针的方法，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针刚好指向链表的中间节点，这种方法的时间复杂度为 O(N)，N 是链表的长度。

代码实现（以 Python 为例）

由于代码部分需要具体的实现细节，这里仅提供一个大致的 Python 代码框架，具体的实现需要根据题目要求进行完善。

class ListNode:
    def __init__(self, address, data, next):
        self.address = address
        self.data = data
        self.next = next
        
def find_middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data if slow else None  # 返回中间节点的数据或 None（如果链表为空）

代码仅为示例，具体的实现需要根据题目要求和输入数据进行调整和完善。