记录每日LeetCode 876.链表的中间结点 Java实现

题目描述

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

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

提示

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

初始代码

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode 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我们返回第二个结点。

参考答案

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
//解法一Java 集合Api
class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        return list.get(list.size() / 2);
    }
}

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
//解法二数组解法
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] node = new ListNode[100];//根据提示创建一个100长度的ListNode数组
        int i = 0;//数组的起始下标
        while(head != null){
            node[i++] = head;
            head = head.next;
        }
        return node[i / 2];
    }
}