leetcode之链表五: 876-链表的中间结点-CSDN博客

本文链接：https://blog.csdn.net/qq_32523587/article/details/116370968

本文介绍了一种通过两次遍历来找到单链表中间节点的方法。首次遍历确定链表长度，再次遍历则根据长度定位到中间节点，并提供了一个具体的Java实现案例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题: https://leetcode-cn.com/problems/middle-of-the-linked-list/

一、题目要求

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

二、解题

package com.leetcode.test.linklist;

public class Solution7 {
    public static void main(String[] args) {
        ListNode a1 = new ListNode(1);
        ListNode a2 = new ListNode(2);
        ListNode a3 = new ListNode(3);
        ListNode a4 = new ListNode(4);
        ListNode a5 = new ListNode(5);
        ListNode a6 = new ListNode(6);
        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;
        a5.next = a6;

        ListNode l = middleNode(a1);

        while (l != null) {
            System.out.print(l.val + " ");
            l = l.next;
        }
    }

    //先遍历第一次，获取链表总长度
    //再遍历第二次，获取中间节点
    public static ListNode middleNode(ListNode head) {
        ListNode cur = head;
        int count = 0;
        //第一次遍历
        while (cur != null){
            count ++;
            cur = cur.next;
        }

        int mid = count/2;
        int pos = 0;        //当前位置
        //第二次遍历
        while (head != null){
            if (pos == mid){
                return head;
            }
            pos ++;
            head = head.next;
        }

        return head;
    }
}