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]