876. 链表的中间结点

题目描述

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

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

输入输出

1
2
3
4
5
6
7
8
9
输入：[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.

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

基本思路

遍历一遍链表 记下链表个数 第二遍取一个新指针走到链表个数/2的位置返回即可

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode middleNode(ListNode head) {
        int cnt = 0;
        ListNode node = head;
        while(node != null){
            cnt++;
            node = node.next;
        }
        int findnode = cnt / 2;
        node = head;
        for(int i = 0; i < findnode; i++){
            node = node.next;
        }
        return node;
    }
}