2023年华为OD机考真题：寻找链表的中间结点

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：寻找链表的中间结点
知识点：链表、数组
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定一个单链表 L，请编写程序输出 L 中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。
例如：给定 L 为 1→7→5，则输出应该为 7；给定 L 为 1→2→3→4，则输出应该为 3。
输入描述：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出链表首结点的地址、结点总个数正整数 N (≤105)。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据(0 ≤ Data ≤ 108)，Next 是下一结点的地址。
输出描述：
对每个测试用例，在一行中输出 L 中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。
补充说明：
已确保输入的结点所构成的链表 L 不会成环，但会存在部分输入结点不属于链表 L 情况。
示例1
输入：
00100 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218
输出：
3
示例2
输入：
10000 3
76892 7 12309
12309 5 -1
10000 1 76892
输出：
7
解题思路：
主要使用链表；

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 寻找链表的中间结点
 * @Description 给定一个单链表 L，请编写程序输出 L 中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。
 * 例如：给定 L 为 1→7→5，则输出应该为 7；给定 L 为 1→2→3→4，则输出应该为 3。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputFirst = sc.nextLine().split(" ");
        int n = Integer.parseInt(inputFirst[1]);

        //用来存放链表数据
        List<String[]> list = new ArrayList<>();
        Node head = null;
        for (int i = 0; i < n; i++) {
            String[] inp = sc.nextLine().split(" ");
            if (inp[0].equals(inputFirst[0])) {
                //头部节点的下一个节点
                Node nextNode = new Node(inp[2], 0, new Node());
                //头部节点
                head = new Node(inp[0], Integer.parseInt(inp[1]), nextNode);
            } else {
                list.add(inp);
            }
        }


        Node node = head;
        while (node.next != null) {
            String addr = node.next.addr;
            for (int i = 0; i < list.size(); i++) {
                String[] strings = list.get(i);
                if (strings[0].equals(addr)) {
                    Node nextNode = null;
                    if (!strings[2].equals("-1")) {       //不等于-1表示有next节点
                        nextNode = new Node(strings[2], 0, new Node());
                    }
                    node.next = new Node(strings[0], Integer.parseInt(strings[1]), nextNode);
                    node = node.next;
                    list.remove(i);     //已经统计过的直接剔除
                    break;
                }
            }
        }

        //快指针（走两步）
        Node fast = head;
        //满指针（走一步）
        Node slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(slow.data);
    }

    static class Node {
        public String addr;
        public int data;
        public Node next;

        public Node() {
            super();
        }

        public Node(String addr, int data, Node next) {
            this.addr = addr;
            this.data = data;
            this.next = next;
        }
    }
}

代码实现二：

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 寻找链表的中间结点
 * @Description 给定一个单链表 L，请编写程序输出 L 中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。
 * 例如：给定 L 为 1→7→5，则输出应该为 7；给定 L 为 1→2→3→4，则输出应该为 3。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        // 通过map快速寻址
        Map<String, Node> map = new HashMap<>();
        Scanner in = new Scanner(System.in);
        // 初始化元信息和具体数据
        String[] mate = in.nextLine().split(" ");
        for (int i = 0; i < Integer.parseInt(mate[1]); i++) {
            String[] info = in.nextLine().split(" ");
            map.put(info[0], new Node(info[1], info[2]));
        }

        // 因为存在为空的数据，通过list保存有效数据和记录数据链长度
        List<String> res = new LinkedList<>();
        String address = mate[0];
        while (map.containsKey(address)) {
            // 记录当前节点，并指向下一个节点
            Node node = map.get(address);
            res.add(node.data);
            address = node.next;
        }

        // 返回中间第二个（如果有）的值
        int idx = (res.size()) / 2;
        System.out.println(res.get(idx));
    }

    public static class Node {
        String data;
        String next;

        public Node(String data, String next) {
            this.data = data;
            this.next = next;
        }
    }
}