codejump
EasyPythonJavaScriptTypeScript

Linked List — Middle of the List

Data StructuresLinked ListTwo Pointers

solve(values) builds a singly linked list from values and returns the values from
the middle node to the end, as an array. With two middle nodes (an even length) the
second one is the middle. An empty list returns [].

You are not allowed to measure the length first: find the middle in a single pass
with a slow and a fast pointer. When the fast pointer (two steps at a time) falls off
the end, the slow pointer (one step at a time) is exactly halfway.

Examples

solve([1,2,3,4,5])    → [3,4,5]
solve([1,2,3,4,5,6])  → [4,5,6]    // two middles: the second one
solve([1,2])          → [2]

Sample tests

Test #1Odd length
Input: [[1,2,3,4,5]]
Output: [3,4,5]
Test #2Even length: second middle
Input: [[1,2,3,4,5,6]]
Output: [4,5,6]
Test #3Two nodes
Input: [[1,2]]
Output: [2]