876. Middle of the Linked List

⭐

題目敘述

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Example 2

Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

ListNode 的 class 內容

// 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; }
}

解題思路

Solution

class Solution {
    public ListNode middleNode(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            list.add(current.val);
            current = current.next;
        }
        int size = list.size();
        int mid = size / 2;
        ListNode result = new ListNode(list.get(mid));
        ListNode temp = result;
        for (int i = mid + 1; i < size; i++) {
            temp.next = new ListNode(list.get(i));
            temp = temp.next;
        }
        return result;
    }
}