Middle of a linked list
You get head, the first node of a linked list with at least one node. Each node is a ListNode with a value (node.val) and a link (node.next) to the node after it.
Return the middle node itself, a node of the given list, not a copy. Counting positions from 0, a list of n nodes has its middle at position n // 2. When n is even, two nodes share the middle, and position n // 2 is the later of the two.
Examples write a linked list as the list of its values: [4, 9, 1] means 4 → 9 → 1. An output is the list that starts at the node you return.
head = [4, 9, 1, 6, 3]Output[1, 6, 3]Five nodes, so the middle is at position 5 // 2 = 2: the node holding 1. From it the list reads 1, 6, 3.
head = [2, 8, 5, 7]Output[5, 7]Four nodes have two middles, 8 and 5. Position 4 // 2 = 2 is the second one, 5.
1 ≤ number of nodes ≤ 100
1 ≤ node value ≤ 100
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.