单链表找中间节点：我的Java解法为何对奇数长度链表失效？

正在解决LeetCode上的单链表找中间节点问题，已知基于列表的解法，但自己的Java代码对奇数长度链表无效，请求分析原因。

ListNode类定义 #

public class ListNode {
 int val;
 ListNode next;
 ListNode() {}
 ListNode(int val) { this.val = val; }
 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

我的源代码 #

public class middle_linked_list {

    public static void main(String args[]){
        ListNode 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);

        System.out.println(middleElement(head).val);
    }

    public static ListNode middleElement(ListNode head){

        int size = 0;
        float counter = 0;
        float middle = 0;

        ListNode mid = head;

        while(head != null)
        {
            ++size;
            head = head.next;
        }

        if(size % 2 == 0){
            middle = size/2f;

        }else{
            middle = Math.round(size/2f);
        }
        
       
        while(mid != null){

            if(counter == middle)
            {
                System.out.println(mid.val);
                return mid;
                
            }

            System.out.println(mid.val);
            ++counter;
            mid = mid.next;

        }


        return null;
    }
}

我的解题思路 #

• 遍历链表获取其长度；
• 定义float类型变量middle；
• 若链表长度为奇数则向上取整，偶数则直接取半；
• 当计数器等于middle时返回对应节点。

问题现象 #

代码对[1,2,3,4]、[1,2,3,4,5,6]等偶数长度链表有效，但对[1,2,3,4,5,6,7]这类奇数长度链表无效。

失效原因分析 #

1. 奇数长度时middle值计算错误

LeetCode对单链表中间节点的要求是：

• 奇数长度时返回正中间节点（如长度7时返回第4个节点，对应0-based索引3）；
• 偶数长度时返回第二个中间节点（如长度4时返回第3个节点，对应0-based索引2）。

你的代码中，奇数长度时用Math.round(size/2f)计算middle：

• 长度5时，size/2f=2.5，Math.round(2.5)返回3（Java中round方法对.5的取值规则是取最近的偶数）；
• 长度7时，size/2f=3.5，Math.round(3.5)返回4。

这导致middle值比正确的0-based索引大1，最终返回的节点偏后。

2. 计数器判断时机与middle值不匹配

你的循环逻辑是先判断counter是否等于middle，再递增counter并移动节点：

• 初始counter=0对应head节点（0-based索引0）；
• 每次判断后，counter才会+1，mid才会移动到下一个节点。

当middle值被错误计算为3（长度5时），循环会在counter=3时返回mid，此时mid已经移动到了索引3的节点（值4），而正确的中间节点是索引2的节点（值3）。

修正方案 #

不需要使用float类型，直接用整数除法即可满足需求：

public static ListNode middleElement(ListNode head){
    int size = 0;
    int counter = 0;
    int middle = 0;

    ListNode mid = head;
    ListNode temp = head;

    // 遍历获取长度
    while(temp != null)
    {
        ++size;
        temp = temp.next;
    }

    // 整数除法直接适配奇偶情况
    middle = size / 2;

    while(mid != null){
        if(counter == middle)
        {
            return mid;
        }
        ++counter;
        mid = mid.next;
    }

    return null;
}

说明：

• 整数除法size/2：长度5时得到2，长度7时得到3，正好对应正确的0-based索引；
• 保持原有判断逻辑，counter等于middle时返回当前mid，正好是目标节点。

另外可以用快慢指针法优化，仅需一次遍历即可找到中间节点，避免两次遍历的开销：

public static ListNode middleElement(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

内容的提问来源于stack exchange，提问作者Khandkar Islam